You are given two 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.
In 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: n = 2 Output: 2 Explanation: We can drop the first egg from floor 1 and the second egg from floor 2. If the first egg breaks, we know that f = 0. If the second egg breaks but the first egg didn't, we know that f = 1. Otherwise, if both eggs survive, we know that f = 2.
Example 2:
Input: n = 100 Output: 14 Explanation: One optimal strategy is: - Drop the 1st egg at floor 9. If it breaks, we know f is between 0 and 8. Drop the 2nd egg starting from floor 1 and going up one at a time to find f within 8 more drops. Total drops is 1 + 8 = 9. - If the 1st egg does not break, drop the 1st egg again at floor 22. If it breaks, we know f is between 9 and 21. Drop the 2nd egg starting from floor 10 and going up one at a time to find f within 12 more drops. Total drops is 2 + 12 = 14. - If the 1st egg does not break again, follow a similar process dropping the 1st egg from floors 34, 45, 55, 64, 72, 79, 85, 90, 94, 97, 99, and 100. Regardless of the outcome, it takes at most 14 drops to determine f.
Constraints:
1 <= n <= 1000Problem Overview: You have two eggs and a building with n floors. An egg breaks if dropped from or above a certain critical floor. The task is to determine that floor using the minimum number of moves in the worst case.
Approach 1: Iterative Strategy Using Triangular Numbers (Time: O(√n), Space: O(1))
The key insight: with two eggs you should drop the first egg using decreasing step sizes. If the first drop is from floor x, the next drop should be x-1 floors above, then x-2, and so on. This ensures that if the egg breaks at some step, the remaining floors can be checked linearly with the second egg within the remaining moves. Mathematically, you need the smallest k such that k(k+1)/2 ≥ n. This triangular number guarantees coverage of all floors within k attempts. Implementation simply increments k until the triangular sum reaches n.
Approach 2: Dynamic Programming (Time: O(n²), Space: O(n))
This approach models the decision process directly using dynamic programming. Let dp[e][f] represent the minimum moves needed with e eggs and f floors. For each floor x, dropping an egg creates two cases: the egg breaks (dp[e-1][x-1]) or it survives (dp[e][f-x]). The worst case of these two outcomes determines the cost of that drop. Iterate over all possible x and take the minimum of 1 + max(...). With only two eggs, the state space stays small, but each floor requires checking many possible drop points, leading to quadratic time.
The triangular number insight comes from analyzing the optimal pattern of drops, which connects the problem to simple math sequences rather than exploring every state.
Recommended for interviews: The triangular-number strategy is the expected optimal solution. It runs in O(√n) time and shows you understand the mathematical structure of the two‑egg constraint. The dynamic programming solution demonstrates the general egg‑dropping recurrence and is useful to explain first before deriving the optimized approach.
We use a strategy based on triangular numbers. With 2 eggs, the first egg is used to reduce the problem to a smaller size. The idea is to find a specific step to drop the first egg such that it reduces the problem optimally. We decrease the number of trials successively by reducing the problem size in each step.
In this C solution, we iteratively check for the smallest number of moves by incrementing the moves and summing them to simulate the sequence of floors to drop from. If the sum of moves covers all n floors, we return the current number of moves.
Time Complexity: O(√n)
Space Complexity: O(1)
We can also solve this problem using dynamic programming by maintaining a table where entry dp[2][j] represents the minimum number of trials needed for 2 eggs and j floors. This approach fills in the table using previous results to efficiently calculate the optimal number of moves.
This C implementation uses dynamic programming. We initialize a dp array for 1 and 2 eggs and iteratively calculate the minimum trials by considering each floor from 1 to n. We check breaking and non-breaking scenarios to update the table with minimum trials.
Time Complexity: O(n²)
Space Complexity: O(n)
We define f[i] to represent the minimum number of operations to determine f in i floors with two eggs. Initially, f[0] = 0, and the rest f[i] = +infty. The answer is f[n].
Considering f[i], we can enumerate the first egg thrown from the j-th floor, where 1 leq j leq i. At this point, there are two cases:
f in j - 1 floors, which requires j - 1 operations. Therefore, the total number of operations is 1 + (j - 1);f in i - j floors, which requires f[i - j] operations. Therefore, the total number of operations is 1 + f[i - j].In summary, we can obtain the state transition equation:
$
f[i] = min_{1 leq j leq i} {1 + max(j - 1, f[i - j])}
Finally, we return f[n].
The time complexity is O(n^2), and the space complexity is O(n). Where n$ is the number of floors.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Iterative Strategy Using Triangular Numbers | Time Complexity: |
| Approach 2: Dynamic Programming | Time Complexity: |
| Dynamic Programming | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Triangular Number Strategy | O(√n) | O(1) | Best solution when eggs = 2. Uses mathematical insight to minimize drops. |
| Dynamic Programming | O(n²) | O(n) | Good for understanding the general egg-dropping recurrence or extending to more eggs. |
1884. Egg Drop With 2 Eggs and N Floors | LEETCODE | DYNAMIC PROGRAMMING | INTERVIEW QUESTION • code Explainer • 8,244 views views
Watch 7 more video solutions →Practice Egg Drop With 2 Eggs and N Floors with our built-in code editor and test cases.
Practice on FleetCode