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.
In this approach, we use dynamic programming (DP) to solve the problem efficiently. The idea is to set up a DP table where dp[k][n] represents the minimum number of moves required to find the critical floor with k eggs and n floors.
We can use binary search to determine which floor to drop the egg from in each step, which helps to optimize the number of trials needed. The recurrence relation can be formulated as:
dp[k][n] = 1 + min(max(dp[k-1][x-1], dp[k][n-x])) for all 1 <= x <= n.
This relation means that for each floor x, you either continue with the remaining floors if the egg doesn't break, or with one fewer egg if it does break. The goal is to find the minimal worst-case scenario.
This C implementation creates a 2D array dp where each entry dp[i][j] represents the minimum number of moves required with i eggs for j floors.
The algorithm initializes the base cases: if there's only one egg, the number of moves is j (since we need to try every floor sequentially), and for zero floors or zero eggs, no move is required.
For each scenario, the function iteratively searches the best floor to drop using binary search, updating the DP table with the minimum number of attempts needed using the recurrence relation explained above.
Time Complexity: O(k * n * log n) because each fill operation of the DP table involves a binary search over the number of floors.
Space Complexity: O(k * n) because of the DP table holding computed results.
Here, we use a mathematical approach combined with dynamic programming. Instead of trying to calculate the minimum number of moves directly, we use a theoretical approach that considers the problem of breaking down moves into binary forms.
We change the problem into one of maximizing the number of floors we can test with a given number of drops. We can calculate m moves where the result is T[k][m] = T[k-1][m-1] + T[k][m-1] + 1. If T[k][m] ≥ n, we found the minimum m.
In this C solution, we use a similar 1D DP concept with two arrays that take shifts for operations. It reduces the grains of move possibilities (instead of examining choice permutations and trays them shallow iterations). For each egg beyond the first, the new entries find a balance between fewer and extra floors, inheriting an O(n) step management budget.
Time Complexity: O(k * n), because we directly shift through combinations.
Space Complexity: O(n) since we're using array-based exploratory floor encoding.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Dynamic Programming with Binary Search | Time Complexity: |
| Mathematical Approach with DP | Time Complexity: |
| Default Approach | — |
| 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 |
花花酱 LeetCode 887. Super Egg Drop - 刷题找工作 EP 348 • Hua Hua • 4,742 views views
Watch 9 more video solutions →Practice Super Egg Drop with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor