Skip to main content
Talentd

Egg Drop With 2 Eggs and N Floors - Solution & Explanation

MediumMathDynamic Programming20 min readAsked at: Microsoft, Google
Practice this problem

Problem Statement

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 <= 1000

Approach Overview

Problem 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.

Approach 1: Approach 1: Iterative Strategy Using Triangular Numbers

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(√n)
Space Complexity: O(1)

Try this approach in the editor →

Approach 2: Approach 2: Dynamic Programming

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n²)
Space Complexity: O(n)

Try this approach in the editor →

Approach 3: Dynamic Programming

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:

  • The egg breaks. At this time, we have one egg left and need to determine f in j - 1 floors, which requires j - 1 operations. Therefore, the total number of operations is 1 + (j - 1);
  • The egg does not break. At this time, we have two eggs left and need to determine 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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Iterative Strategy Using Triangular Numbers

Time Complexity: O(√n)
Space Complexity: O(1)

Approach 2: Dynamic Programming

Time Complexity: O(n²)
Space Complexity: O(n)

Dynamic Programming—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Iterative Triangular Number StrategyO(√n)O(1)Best solution when eggs = 2. Uses mathematical insight to minimize drops.
Dynamic ProgrammingO(n²)O(n)Good for understanding the general egg-dropping recurrence or extending to more eggs.

Video Solution

1884. Egg Drop With 2 Eggs and N Floors | LEETCODE | DYNAMIC PROGRAMMING | INTERVIEW QUESTION • code Explainer • 8,350 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is Egg Drop With 2 Eggs and N Floors easy or hard?
The problem is rated Medium because the naive dynamic programming solution is straightforward but inefficient. Recognizing the triangular-number pattern that reduces the complexity to O(√n) requires deeper insight into the drop strategy.
Egg Drop With 2 Eggs and N Floors Python/Java solution
Most implementations compute the smallest k where k(k+1)/2 ≥ n using a loop or math formula. This logic is easy to implement in Python, Java, C++, or JavaScript and runs in constant space with only a few integer variables.
How to solve Egg Drop With 2 Eggs and N Floors in O(n)?
A better solution actually runs in O(√n). Compute the minimum k where the triangular number k(k+1)/2 covers all n floors. Each drop reduces the remaining search space by one fewer floor, ensuring the worst-case number of moves stays within k.
What is the best approach for Egg Drop With 2 Eggs and N Floors?
The optimal approach uses a triangular number strategy. Find the smallest k such that k(k+1)/2 ≥ n. This guarantees you can determine the critical floor within k drops in the worst case. The method runs in O(√n) time and O(1) space and is the most efficient solution for the two‑egg constraint.
Is Egg Drop With 2 Eggs and N Floors asked at Google/Amazon/Meta?
Egg dropping problems frequently appear in interviews at companies like Google, Amazon, and Microsoft. The two‑egg variant is a common medium-level version used to test dynamic programming reasoning and mathematical optimization.
What data structure is used in Egg Drop With 2 Eggs and N Floors?
The dynamic programming approach uses a 2D DP table where dp[e][f] stores the minimum moves for e eggs and f floors. The optimal triangular-number solution relies on mathematical iteration and does not require additional data structures.
What is the time complexity of Egg Drop With 2 Eggs and N Floors?
The optimal triangular-number approach runs in O(√n) time because the required number of moves k grows roughly as √(2n). The dynamic programming formulation takes O(n²) time since it checks every possible drop floor for each state.

Ready to solve this problem?

Practice Egg Drop With 2 Eggs and N Floors with our built-in code editor and test cases.

Practice on FleetCode
Previous

Super Egg Drop