Watch 10 video solutions for Super Egg Drop, a hard level problem involving Math, Binary Search, Dynamic Programming. This walkthrough by Hua Hua has 4,742 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 1001 <= n <= 104Problem Overview: You are given K eggs and a building with N floors. An egg breaks if dropped from a floor higher than a certain threshold. The goal is to determine the minimum number of moves required to find that threshold floor in the worst case.
Approach 1: Dynamic Programming with Binary Search (Time: O(K * N * log N), Space: O(K * N))
This approach models the problem with a DP state dp[k][n], representing the minimum moves needed with k eggs and n floors. For each floor x you drop an egg from, two outcomes occur: the egg breaks (search below with k-1 eggs) or it survives (search above with k eggs). The worst-case cost becomes 1 + max(dp[k-1][x-1], dp[k][n-x]). Instead of checking every floor linearly, apply binary search because one side increases while the other decreases as x grows. This optimization significantly reduces transitions while keeping the DP formulation intuitive. Use this approach when you want a clear state definition and standard dynamic programming reasoning.
Approach 2: Mathematical DP on Moves (Time: O(K * log N), Space: O(K))
A more efficient formulation focuses on the number of moves instead of floors. Let dp[m][k] represent the maximum number of floors that can be tested with m moves and k eggs. The recurrence becomes dp[m][k] = dp[m-1][k-1] + dp[m-1][k] + 1. The first term represents the case where the egg breaks, the second where it survives, and the +1 accounts for the current floor. Increase the move count until dp[m][K] >= N. This works because each move expands the searchable range combinatorially. The logic relies on mathematical observation rather than floor-by-floor simulation, making it both elegant and fast. Concepts here intersect with combinatorics and mathematical reasoning.
Recommended for interviews: The mathematical DP approach is typically expected in strong interviews because it reduces the complexity to roughly O(K log N) and shows deeper insight into the problem structure. Still, starting with the DP state definition and explaining the binary-search optimization demonstrates solid dynamic programming fundamentals before presenting the optimal idea.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with Binary Search | O(K * N * log N) | O(K * N) | When explaining classic DP state transitions and optimizing the drop-floor search with binary search |
| Mathematical DP on Moves | O(K * log N) | O(K) | Best for optimal performance and interviews where mathematical insight into the problem is expected |