Super Egg Drop

Problem

You are given k identical eggs and you have access to a building with n floors labeled from 1 to n.

You know that there exists a floor f where 0 <= f <= n such that any egg dropped at a floor higher than f will break, and any egg dropped at or below floor f will not break.

Each move, you may take an unbroken egg and drop it from any floor x (where 1 <= x <= n). If the egg breaks, you can no longer use it. However, if the egg does not break, you may reuse it in future moves.

Return the minimum number of moves that you need to determine with certainty what the value of f is.

Examples

Example 1:

Input: k = 1, n = 2
Output: 2
Explanation: 
Drop the egg from floor 1. If it breaks, we know that f = 0.
Otherwise, drop the egg from floor 2. If it breaks, we know that f = 1.
If it does not break, then we know f = 2.
Hence, we need at minimum 2 moves to determine with certainty what the value of f is.

Example 2:

Input: k = 2, n = 6
Output: 3

Example 3:

Input: k = 3, n = 14
Output: 4

Solution

Method 1 - Naive Recursion (Exponential)

Intuition

Brute-force every possible first drop floor x (1..h). For each x we consider two outcomes: egg breaks (search below with one fewer egg) or egg survives (search above with same eggs). We take the worse (max) because we require certainty, then choose the x that minimizes this worst-case.

Approach

• Define f(e,h) recursively with base cases.
• Enumerate all x.
• Return the minimum worst-case cost.

Recurrence

f(1,h) = h
f(e,0) = 0, f(e,1) = 1
f(e,h) = 1 + min_{1<=x<=h} max( f(e-1, x-1), f(e, h-x) )

Code

C++

class SolutionNaive {
public:
    int superEggDrop(int k, int n) { return solve(k, n); }
private:
    int solve(int e, int h) {
        if (h == 0 || h == 1) return h;
        if (e == 1) return h;
        int best = INT_MAX;
        for (int x = 1; x <= h; ++x) {
            int broken = solve(e - 1, x - 1);
            int survive = solve(e, h - x);
            int worst = 1 + std::max(broken, survive);
            if (worst < best) best = worst;
        }
        return best;
    }
};

Java

class SolutionNaive {
    public int superEggDrop(int k, int n) { return solve(k, n); }
    private int solve(int e, int h) {
        if (h == 0 || h == 1) return h;
        if (e == 1) return h;
        int best = Integer.MAX_VALUE;
        for (int x = 1; x <= h; x++) {
            int broken = solve(e - 1, x - 1);
            int survive = solve(e, h - x);
            int worst = 1 + Math.max(broken, survive);
            if (worst < best) best = worst;
        }
        return best;
    }
}

Python

class SolutionNaive:
    def superEggDrop(self, k: int, n: int) -> int:
        def solve(e: int, h: int) -> int:
            if h <= 1:
                return h
            if e == 1:
                return h
            best = float('inf')
            for x in range(1, h + 1):
                worst = 1 + max(solve(e - 1, x - 1), solve(e, h - x))
                if worst < best:
                    best = worst
            return best
        return solve(k, n)

Complexity

• ⏰ Time complexity: O(h^e) – exponential; explores all partitions; severe recomputation.
• 🧺 Space complexity: O(h) – recursion depth.

Method 2 - Top-Down Memoization

Intuition

Caches the exponential recursion’s overlapping subproblems. Still scans every x per state so quadratic in floors per egg count.

Approach

• Same recurrence; add memo (hash map / 2D array / decorator).
• Optionally could binary-search x (monotonic broken vs survive curves) to reduce to O(k * n * log n); here we keep full scan for clarity.

Recurrence

Same as Method 1.

Code

C++

class SolutionMemo {
    std::vector<std::vector<int>> memo; // -1 = uncomputed
public:
    int superEggDrop(int k, int n) {
        memo.assign(k+1, std::vector<int>(n+1, -1));
        return solve(k, n);
    }
private:
    int solve(int e, int h) {
        if (h <= 1) return h;
        if (e == 1) return h;
        int &ref = memo[e][h];
        if (ref != -1) return ref;
        int best = INT_MAX;
        for (int x = 1; x <= h; ++x) {
            int broken = solve(e - 1, x - 1);
            int survive = solve(e, h - x);
            int worst = 1 + std::max(broken, survive);
            if (worst < best) best = worst;
        }
        return ref = best;
    }
};

Java

import java.util.Arrays;
class SolutionMemo {
    private int[][] memo;
    public int superEggDrop(int k, int n) {
        memo = new int[k+1][n+1];
        for (int[] row : memo) Arrays.fill(row, -1);
        return solve(k, n);
    }
    private int solve(int e, int h) {
        if (h <= 1) return h;
        if (e == 1) return h;
        if (memo[e][h] != -1) return memo[e][h];
        int best = Integer.MAX_VALUE;
        for (int x = 1; x <= h; x++) {
            int broken = solve(e - 1, x - 1);
            int survive = solve(e, h - x);
            int worst = 1 + Math.max(broken, survive);
            if (worst < best) best = worst;
        }
        return memo[e][h] = best;
    }
}

Python

from functools import lru_cache

class SolutionMemo:
    def superEggDrop(self, k: int, n: int) -> int:
        @lru_cache(None)
        def solve(e: int, h: int) -> int:
            if h <= 1:
                return h
            if e == 1:
                return h
            best = float('inf')
            for x in range(1, h + 1):
                worst = 1 + max(solve(e - 1, x - 1), solve(e, h - x))
                if worst < best:
                    best = worst
            return best
        return solve(k, n)

Complexity

• ⏰ Time complexity: O(k * n^2) – k * n states × up to n trial floors each.
• 🧺 Space complexity: O(k * n) – memo plus recursion stack O(k + n).

Method 3 - Bottom-Up DP (Tabulation with Binary Search)

Intuition

Fill dp[e][h] using recurrence. For fixed (e,h), broken(x)=dp[e-1][x-1] increases with x; survive(x)=dp[e][h-x] decreases with x. The maximum of a non-decreasing and a non-increasing sequence is unimodal → binary search finds optimal x.

Approach

1. Initialize base row/columns.
2. For each eggs e and floors h, binary search pivot.
3. Use pivot to compute dp[e][h].

Recurrence

dp[e][h] = 1 + min_{1<=x<=h} max( dp[e-1][x-1], dp[e][h-x] )

Code

C++

class Solution {
public:
    int superEggDrop(int K, int N) {
        std::vector<std::vector<int>> dp(K+1, std::vector<int>(N+1, 0));
        for (int h = 0; h <= N; ++h) dp[1][h] = h;
        for (int e = 2; e <= K; ++e) {
            dp[e][1] = 1;
            for (int h = 2; h <= N; ++h) {
                int lo = 1, hi = h;
                while (lo < hi) {
                    int mid = (lo + hi) / 2;
                    int broken = dp[e-1][mid-1];
                    int survive = dp[e][h-mid];
                    if (broken < survive) lo = mid + 1; else hi = mid;
                }
                dp[e][h] = 1 + dp[e-1][lo-1];
            }
        }
        return dp[K][N];
    }
};

Go

func superEggDrop(k int, n int) int {
    dp := make([][]int, k+1)
    for i := range dp { dp[i] = make([]int, n+1) }
    for h := 0; h <= n; h++ { dp[1][h] = h }
    for e := 2; e <= k; e++ {
        dp[e][1] = 1
        for h := 2; h <= n; h++ {
            lo, hi := 1, h
            for lo < hi {
                mid := (lo + hi) / 2
                broken := dp[e-1][mid-1]
                survive := dp[e][h-mid]
                if broken < survive { lo = mid + 1 } else { hi = mid }
            }
            dp[e][h] = 1 + dp[e-1][lo-1]
        }
    }
    return dp[k][n]
}

Java

class Solution {
    public int superEggDrop(int k, int n) {
        int[][] dp = new int[k + 1][n + 1];
        for (int h = 0; h <= n; h++) dp[1][h] = h;
        for (int e = 2; e <= k; e++) {
            dp[e][1] = 1;
            for (int h = 2; h <= n; h++) {
                int lo = 1, hi = h;
                while (lo < hi) {
                    int mid = (lo + hi) / 2;
                    int broken = dp[e - 1][mid - 1];
                    int survive = dp[e][h - mid];
                    if (broken < survive) lo = mid + 1; else hi = mid;
                }
                dp[e][h] = 1 + dp[e - 1][lo - 1];
            }
        }
        return dp[k][n];
    }
}

Python

class Solution:
    def superEggDrop(self, k: int, n: int) -> int:
        dp = [[0]*(n+1) for _ in range(k+1)]
        for h in range(n+1):
            dp[1][h] = h
        for e in range(2, k+1):
            dp[e][1] = 1
            for h in range(2, n+1):
                lo, hi = 1, h
                while lo < hi:
                    mid = (lo + hi)//2
                    broken = dp[e-1][mid-1]
                    survive = dp[e][h-mid]
                    if broken < survive:
                        lo = mid + 1
                    else:
                        hi = mid
                dp[e][h] = 1 + dp[e-1][lo-1]
        return dp[k][n]

Kotlin

class SolutionKt {
    fun superEggDrop(k: Int, n: Int): Int {
        val dp = Array(k+1) { IntArray(n+1) }
        for (h in 0..n) dp[1][h] = h
        for (e in 2..k) {
            dp[e][1] = 1
            for (h in 2..n) {
                var lo = 1; var hi = h
                while (lo < hi) {
                    val mid = (lo + hi) / 2
                    val broken = dp[e-1][mid-1]
                    val survive = dp[e][h-mid]
                    if (broken < survive) lo = mid + 1 else hi = mid
                }
                dp[e][h] = 1 + dp[e-1][lo-1]
            }
        }
        return dp[k][n]
    }
}

Rust

impl Solution {
    pub fn super_egg_drop(k: i32, n: i32) -> i32 {
        let k = k as usize; let n = n as usize;
        let mut dp = vec![vec![0; n+1]; k+1];
        for h in 0..=n { dp[1][h] = h as i32; }
        for e in 2..=k {
            dp[e][1] = 1;
            for h in 2..=n {
                let (mut lo, mut hi) = (1usize, h);
                while lo < hi {
                    let mid = (lo + hi)/2;
                    let broken = dp[e-1][mid-1];
                    let survive = dp[e][h-mid];
                    if broken < survive { lo = mid + 1; } else { hi = mid; }
                }
                dp[e][h] = 1 + dp[e-1][lo-1];
            }
        }
        dp[k][n]
    }
}

TypeScript

class SolutionTS {
    superEggDrop(k: number, n: number): number {
        const dp: number[][] = Array.from({length: k+1}, () => Array(n+1).fill(0));
        for (let h = 0; h <= n; h++) dp[1][h] = h;
        for (let e = 2; e <= k; e++) {
            dp[e][1] = 1;
            for (let h = 2; h <= n; h++) {
                let lo = 1, hi = h;
                while (lo < hi) {
                    const mid = Math.floor((lo + hi)/2);
                    const broken = dp[e-1][mid-1];
                    const survive = dp[e][h-mid];
                    if (broken < survive) lo = mid + 1; else hi = mid;
                }
                dp[e][h] = 1 + dp[e-1][lo-1];
            }
        }
        return dp[k][n];
    }
}

Complexity

• ⏰ Time complexity: O(k * n * log n) – per state binary search.
• 🧺 Space complexity: O(k * n) – DP table.