Super Egg Drop

Hard

#0841Time: O(k * n^2). We have three nested loops: `k` eggs, `n` floors, and a linear scan of `n` possible drop floors.Space: O(k * n) for the 2D DP table.

Patterns

Math Dynamic Programming

Algorithms

Binary Search

Prompt

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.

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

Constraints:

1 <= k <= 100
1 <= n <= 10⁴

Approaches

3 approaches with complexity analysis and trade-offs.

This approach uses dynamic programming to solve the problem. We define a function dp(k, n) which represents the minimum number of moves required to determine the critical floor f with k eggs and n floors. The goal is to find dp(K, N) by building a DP table.

Algorithm

Create a 2D array dp of size (k+1) x (n+1).
Initialize base cases: dp[i][0] = 0 for all i, and dp[1][j] = j for all j.
Iterate for eggs i from 2 to k.
Iterate for floors j from 1 to n.
Inside this loop, iterate for the drop floor x from 1 to j.
Calculate moves = 1 + max(dp[i-1][x-1], dp[i][j-x]).
Update dp[i][j] = min(dp[i][j], moves).
The final answer is dp[k][n].

Walkthrough

Let dp[i][j] be the minimum number of moves needed for i eggs and j floors. When we drop an egg from floor x (where 1 <= x <= j), there are two outcomes:

The egg breaks: We have i-1 eggs left and need to check the x-1 floors below. The number of moves required is dp[i-1][x-1].
The egg survives: We still have i eggs and need to check the j-x floors above. The number of moves required is dp[i][j-x].

Since we need to find the solution for the worst-case scenario, the number of moves for a drop from floor x is 1 + max(dp[i-1][x-1], dp[i][j-x]). To find the minimum moves for j floors, we must choose the floor x that minimizes this worst-case value. This leads to the recurrence relation: dp[i][j] = 1 + min_{1 <= x <= j} { max(dp[i-1][x-1], dp[i][j-x]) }.

Base Cases:

dp[i][0] = 0 (0 floors, 0 moves).
dp[1][j] = j (1 egg, j floors, we must check linearly from floor 1 to j).

We can build a 2D DP table of size (k+1) x (n+1) to store the results and compute them iteratively.

1class Solution {2    public int superEggDrop(int k, int n) {3        int[][] dp = new int[k + 1][n + 1];4        for (int j = 1; j <= n; j++) {5            dp[1][j] = j;6        }7        for (int i = 1; i <= k; i++) {8            dp[i][0] = 0;9        }10 11        for (int i = 2; i <= k; i++) {12            for (int j = 1; j <= n; j++) {13                dp[i][j] = Integer.MAX_VALUE;14                for (int x = 1; x <= j; x++) {15                    int moves = 1 + Math.max(dp[i - 1][x - 1], dp[i][j - x]);16                    dp[i][j] = Math.min(dp[i][j], moves);17                }18            }19        }20        return dp[k][n];21    }22}

Complexity

Time

O(k * n^2). We have three nested loops: `k` eggs, `n` floors, and a linear scan of `n` possible drop floors.

Space

O(k * n) for the 2D DP table.

Trade-offs

Pros

Conceptually straightforward application of dynamic programming.
Correctly solves the problem by exploring all possibilities.

Cons

The time complexity is too high for the given constraints (n up to 10000), leading to a "Time Limit Exceeded" error on most platforms.

This approach improves upon the previous DP solution. We observe that in the recurrence dp[i][j] = 1 + min_{1 <= x <= j} { max(dp[i-1][x-1], dp[i][j-x]) }, the term dp[i-1][x-1] is monotonically increasing with x, while dp[i][j-x] is monotonically decreasing with x. This property allows us to use binary search to find the optimal drop floor x.

Algorithm

Create a 2D array dp of size (k+1) x (n+1).
Initialize base cases: dp[i][0] = 0 and dp[1][j] = j.
Iterate for eggs i from 2 to k.
Iterate for floors j from 1 to n.
Inside this loop, use binary search on x (from low=1 to high=j) to find the minimum value of 1 + max(dp[i-1][x-1], dp[i][j-x]).
Store this minimum value in dp[i][j].
The final answer is dp[k][n].

Walkthrough

The state and recurrence relation are the same as the previous approach. The key insight is to optimize the search for the optimal drop floor x. Let f1(x) = dp[i-1][x-1] (increasing) and f2(x) = dp[i][j-x] (decreasing). We want to find min(max(f1(x), f2(x))). The minimum of the maximum of an increasing and a decreasing function occurs where they are closest, i.e., near their intersection point. Instead of a linear scan for x from 1 to j, we can use binary search to find the optimal x that minimizes max(f1(x), f2(x)). For a given mid in the binary search (representing the drop floor x), we compare dp[i-1][mid-1] and dp[i][j-mid].

If dp[i-1][mid-1] < dp[i][j-mid], the intersection point is to the right, so we search in the range [mid+1, high].
If dp[i-1][mid-1] > dp[i][j-mid], the intersection point is to the left, so we search in the range [low, mid-1]. This optimization reduces the time to find the optimal x from O(j) to O(log j).

1class Solution {2    public int superEggDrop(int k, int n) {3        int[][] dp = new int[k + 1][n + 1];4        for (int j = 1; j <= n; j++) {5            dp[1][j] = j;6        }7 8        for (int i = 2; i <= k; i++) {9            for (int j = 1; j <= n; j++) {10                int low = 1, high = j;11                int result = j;12                while (low <= high) {13                    int mid = low + (high - low) / 2;14                    int breakCase = dp[i - 1][mid - 1];15                    int noBreakCase = dp[i][j - mid];16                    int moves = 1 + Math.max(breakCase, noBreakCase);17                    result = Math.min(result, moves);18 19                    if (breakCase > noBreakCase) {20                        high = mid - 1;21                    } else {22                        low = mid + 1;23                    }24                }25                dp[i][j] = result;26            }27        }28        return dp[k][n];29    }30}

Complexity

Time

O(k * n * log n). The two outer loops run in `O(k*n)` and the inner binary search takes `O(log n)`.

Space

O(k * n) for the 2D DP table.

Trade-offs

Pros

Significantly faster than the quadratic approach.
Passes more test cases and is often sufficient for medium constraints.

Cons

The time complexity can still be a bottleneck for the largest constraints.
Space complexity is still high at O(k * n).

This approach rephrases the problem. Instead of asking "what is the minimum number of moves for k eggs and n floors?", we ask "what is the maximum number of floors we can check with k eggs and m moves?". This change of perspective leads to a more efficient solution.

Algorithm

Create a 1D array dp of size k+1 to store the maximum floors checkable for the current number of moves. Initialize it to zeros.
Initialize moves = 0.
Start a loop that continues as long as dp[k] < n.
Inside the loop, increment moves.
Update the dp array for the current number of moves. Iterate j from k down to 1. The backward iteration is crucial to use the dp values from the previous move count.
The update rule is dp[j] = 1 + dp[j] + dp[j-1].
Once the loop terminates (i.e., dp[k] >= n), the value of moves is the minimum number of moves required.

Walkthrough

Let dp[m][k] be the maximum number of floors we can check with m moves and k eggs. If we make a move by dropping an egg from some floor x, there are two outcomes:

Egg breaks: We have m-1 moves and k-1 eggs left. We can check dp[m-1][k-1] floors below x.
Egg survives: We have m-1 moves and k eggs left. We can check dp[m-1][k] floors above x.

Therefore, the total number of floors we can check is the sum of floors below x, floor x itself, and floors above x. This gives the recurrence relation: dp[m][k] = 1 + dp[m-1][k-1] + dp[m-1][k]. Our goal is to find the smallest number of moves m such that dp[m][k] >= n. We can compute dp[m][k] for increasing m (moves) starting from 1, until dp[m][k] is large enough to cover all n floors.

Space Optimization: Notice that dp[m][k] only depends on the values from the previous number of moves, m-1. This means we can optimize the space from a 2D array O(m*k) to a 1D array O(k). The recurrence becomes dp[k] = 1 + dp_previous[k-1] + dp_previous[k].

1class Solution {2    public int superEggDrop(int k, int n) {3        // dp[j] will be the max floors we can check with j eggs and `moves` moves.4        int[] dp = new int[k + 1];5        int moves = 0;6        while (dp[k] < n) {7            moves++;8            // Iterate backwards to use results from the previous move count9            for (int j = k; j > 0; j--) {10                // dp[j] (new) = 1 (current floor) + dp[j] (old, for no-break) + dp[j-1] (old, for break)11                dp[j] = 1 + dp[j] + dp[j - 1];12            }13        }14        return moves;15    }16}

Complexity

Time

O(k * m) where `m` is the final answer (number of moves). In the worst case, `m` can be up to `n` (when `k=1`), so the complexity is `O(k * n)`. However, `m` is much smaller than `n` for larger `k`. Specifically, `m` is approximately `O(log n)` when `k` is large enough (`k > log2(n)`), making the complexity closer to `O(k * log n)`. The overall upper bound is `O(k*n)`.

Space

O(k) for the 1D DP array.

Trade-offs

Pros

This is the most efficient approach in terms of both time and space complexity.
The logic is elegant once the problem is rephrased.

Cons

The change in perspective from the original problem statement might not be immediately obvious.

Solutions

Solution

1class Solution {2private3  int[][] f;4public5  int superEggDrop(int k, int n) {6    f = new int[n + 1][k + 1];7    return dfs(n, k);8  }9private10  int dfs(int i, int j) {11    if (i < 1) {12      return 0;13    }14    if (j == 1) {15      return i;16    }17    if (f[i][j] != 0) {18      return f[i][j];19    }20    int l = 1, r = i;21    while (l < r) {22      int mid = (l + r + 1) >> 1;23      int a = dfs(mid - 1, j - 1);24      int b = dfs(i - mid, j);25      if (a <= b) {26        l = mid;27      } else {28        r = mid - 1;29      }30    }31    return f[i][j] = Math.max(dfs(l - 1, j - 1), dfs(i - l, j)) + 1;32  }33}

1class Solution {2public:3  int superEggDrop(int k, int n) {4    int f[n + 1][k + 1];5    memset(f, 0, sizeof(f));6    function<int(int, int)> dfs = [&](int i, int j) -> int {7      if (i < 1) {8        return 0;9      }10      if (j == 1) {11        return i;12      }13      if (f[i][j]) {14        return f[i][j];15      }16      int l = 1, r = i;17      while (l < r) {18        int mid = (l + r + 1) >> 1;19        int a = dfs(mid - 1, j - 1);20        int b = dfs(i - mid, j);21        if (a <= b) {22          l = mid;23        } else {24          r = mid - 1;25        }26      }27      return f[i][j] = max(dfs(l - 1, j - 1), dfs(i - l, j)) + 1;28    };29    return dfs(n, k);30  }31};

1class Solution:2    def superEggDrop(self, k: int, n: int) -> int: @ cache def dfs(i: int, j: int) -> int: if i < 1: return 0 if j == 1: return i l, r = 1, i while l < r: mid = (l + r + 1) >> 1 a = dfs(mid - 1, j - 1) b = dfs(i - mid, j) if a <= b: l = mid else: r = mid - 1 return max(dfs(l - 1, j - 1), dfs(i - l, j)) + 1 return dfs(n, k)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution {2private3  int[][] f;4public5  int superEggDrop(int k, int n) {6    f = new int[n + 1][k + 1];7    return dfs(n, k);8  }9private10  int dfs(int i, int j) {11    if (i < 1) {12      return 0;13    }14    if (j == 1) {15      return i;16    }17    if (f[i][j] != 0) {18      return f[i][j];19    }20    int l = 1, r = i;21    while (l < r) {22      int mid = (l + r + 1) >> 1;23      int a = dfs(mid - 1, j - 1);24      int b = dfs(i - mid, j);25      if (a <= b) {26        l = mid;27      } else {28        r = mid - 1;29      }30    }31    return f[i][j] = Math.max(dfs(l - 1, j - 1), dfs(i - l, j)) + 1;32  }33}

1class Solution {2public:3  int superEggDrop(int k, int n) {4    int f[n + 1][k + 1];5    memset(f, 0, sizeof(f));6    function<int(int, int)> dfs = [&](int i, int j) -> int {7      if (i < 1) {8        return 0;9      }10      if (j == 1) {11        return i;12      }13      if (f[i][j]) {14        return f[i][j];15      }16      int l = 1, r = i;17      while (l < r) {18        int mid = (l + r + 1) >> 1;19        int a = dfs(mid - 1, j - 1);20        int b = dfs(i - mid, j);21        if (a <= b) {22          l = mid;23        } else {24          r = mid - 1;25        }26      }27      return f[i][j] = max(dfs(l - 1, j - 1), dfs(i - l, j)) + 1;28    };29    return dfs(n, k);30  }31};

1class Solution:2    def superEggDrop(self, k: int, n: int) -> int: @ cache def dfs(i: int, j: int) -> int: if i < 1: return 0 if j == 1: return i l, r = 1, i while l < r: mid = (l + r + 1) >> 1 a = dfs(mid - 1, j - 1) b = dfs(i - mid, j) if a <= b: l = mid else: r = mid - 1 return max(dfs(l - 1, j - 1), dfs(i - l, j)) + 1 return dfs(n, k)

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.