Egg Drop With 2 Eggs and N Floors solution and explanation
Google
7 more videos on this problem
1884. Egg Drop With 2 Eggs and N Floors | LEETCODE | DYNAMIC PROGRAMMING | INTERVIEW QUESTIONcode Explainer · 11:55 · 8K views
1884. Egg Drop With 2 Eggs and N Floors (Leetcode Medium)Programming Live with Larry · 10:05 · 1K views
dynamic programming c++ solution to leetcode problem 1884 egg dropleetcode blind 75 · 3:04 · 1K views
1884.Egg Drop with 2 Eggs and N floors |leetcode dp series|leetcodeDp wale · 11:52 · 695 views
1884. Egg Drop With 2 Eggs and N Floors - Daily Leetcode (Day 11)yeetcode · 26:37 · 472 views
Leetcode 1884. Egg Drop With 2 Eggs and N Floors || DPExpertFunda · 15:30 · 276 views
Leetcode 1884. Egg Drop With 2 Eggs and N Floors讲解fengshuo li · 9:08 · 223 views
LeetCode 1884: Egg Drop With 2 Eggs and N FloorsAlitaCode · 27:54 · 1 view
The problem
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.
def eggDrop(n):
m = 0
drop = 0
while drop < n:
m += 1
drop += m
return m
n = 100
print(f"Minimum number of drops for {n} floors is {eggDrop(n)}")public class EggDrop {
public static int eggDrop(int n) {
int m = 0, drop = 0;
while (drop < n) {
m++;
drop += m;
}
return m;
}
public static void main(String[] args) {
int n = 100;
System.out.println("Minimum number of drops for " + n + " floors is " + eggDrop(n));
}
}#include <iostream>
#include <cmath>
int eggDrop(int n) {
int m = 0, drop = 0;
while (drop < n) {
m++;
drop += m;
}
return m;
}
int main() {
int n = 100;
std::cout << "Minimum number of drops for " << n << " floors is " << eggDrop(n) << std::endl;
return 0;
}function eggDrop(n) {
let m = 0, drop = 0;
while (drop < n) {
m++;
drop += m;
}
return m;
}
const n = 100;
console.log(`Minimum number of drops for ${n} floors is ${eggDrop(n)}`);#include <math.h>
#include <stdio.h>
int eggDrop(int n) {
int m = 0, drop = 0;
while (drop < n) {
m++;
drop += m;
}
return m;
}
int main() {
int n = 100;
printf("Minimum number of drops for %d floors is %d\n", n, eggDrop(n));
return 0;
}using System;
class EggDrop {
public static int EggDropCalc(int n) {
int m = 0, drop = 0;
while (drop < n) {
m++;
drop += m;
}
return m;
}
static void Main() {
int n = 100;
Console.WriteLine("Minimum number of drops for " + n + " floors is " + EggDropCalc(n));
}
}The Python solution efficiently calculates the number of moves by incrementally checking the necessary drops using a simple loop to cover all floors. The loop terminates when the sum exceeds n.
Time Complexity: O(√n)
Space Complexity: O(1)
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.
def eggDrop(n):
dp = [[0 for x in range(n+1)] for x in range(3)]
for i in range(1, 3):
dp[i][1] = 1
dp[i][0] = 0
for j in range(1, n+1):
dp[1][j] = j
for i in range(2, 3):
for j in range(2, n+1):
dp[i][j] = float('inf')
for x in range(1, j+1):
res = 1 + max(dp[i-1][x-1], dp[i][j-x])
dp[i][j] = min(dp[i][j], res)
return dp[2][n]
n = 100
print(f"Minimum number of drops for {n} floors is {eggDrop(n)}")public class EggDropDP {
public static int eggDrop(int n) {
int[][] dp = new int[3][n + 1];
for (int i = 1; i <= 2; i++) {
dp[i][0] = 0;
dp[i][1] = 1;
}
for (int j = 2; j <= n; j++)
dp[1][j] = j;
for (int i = 2; i <= 2; i++) {
for (int j = 2; j <= n; j++) {
dp[i][j] = Integer.MAX_VALUE;
for (int x = 1; x <= j; x++) {
int res = 1 + Math.max(dp[i - 1][x - 1], dp[i][j - x]);
dp[i][j] = Math.min(dp[i][j], res);
}
}
}
return dp[2][n];
}
public static void main(String[] args) {
int n = 100;
System.out.println("Minimum number of drops for " + n + " floors is " + eggDrop(n));
}
}#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int eggDrop(int n) {
vector<vector<int>> dp(3, vector<int>(n + 1, 0));
for (int i = 1; i <= 2; i++) {
dp[i][0] = 0;
dp[i][1] = 1;
}
for (int j = 2; j <= n; j++)
dp[1][j] = j;
for (int i = 2; i <= 2; i++) {
for (int j = 2; j <= n; j++) {
dp[i][j] = INT_MAX;
for (int x = 1; x <= j; x++) {
int res = 1 + max(dp[i - 1][x - 1], dp[i][j - x]);
dp[i][j] = min(dp[i][j], res);
}
}
}
return dp[2][n];
}
int main() {
int n = 100;
cout << "Minimum number of drops for " << n << " floors is " << eggDrop(n) << endl;
return 0;
}function eggDrop(n) {
let dp = Array.from({ length: 3 }, () => Array(n + 1).fill(0));
for (let i = 1; i <= 2; i++) {
dp[i][0] = 0;
dp[i][1] = 1;
}
for (let j = 2; j <= n; j++)
dp[1][j] = j;
for (let i = 2; i <= 2; i++) {
for (let j = 2; j <= n; j++) {
dp[i][j] = Infinity;
for (let x = 1; x <= j; x++) {
const res = 1 + Math.max(dp[i - 1][x - 1], dp[i][j - x]);
dp[i][j] = Math.min(dp[i][j], res);
}
}
}
return dp[2][n];
}
const n = 100;
console.log(`Minimum number of drops for ${n} floors is ${eggDrop(n)}`);#include <stdio.h>
#include <limits.h>
int min(int a, int b) {
return a < b ? a : b;
}
int eggDrop(int n) {
int dp[3][n + 1];
int i, j, x, res;
for (i = 1; i <= 2; i++) {
dp[i][0] = 0;
dp[i][1] = 1;
}
for (j = 2; j <= n; j++)
dp[1][j] = j;
for (i = 2; i <= 2; i++) {
for (j = 2; j <= n; j++) {
dp[i][j] = INT_MAX;
for (x = 1; x <= j; x++) {
res = 1 + max(dp[i - 1][x - 1], dp[i][j - x]);
if (res < dp[i][j]) dp[i][j] = res;
}
}
}
return dp[2][n];
}
int main() {
int n = 100;
printf("Minimum number of drops for %d floors is %d\n", n, eggDrop(n));
return 0;
}using System;
class EggDropDP {
public static int EggDrop(int n) {
int[,] dp = new int[3, n + 1];
for (int i = 1; i <= 2; i++) {
dp[i, 1] = 1;
dp[i, 0] = 0;
}
for (int j = 2; j <= n; j++)
dp[1, j] = j;
for (int i = 2; i <= 2; i++) {
for (int j = 2; j <= n; j++) {
dp[i, j] = int.MaxValue;
for (int x = 1; x <= j; x++) {
int res = 1 + Math.Max(dp[i - 1, x - 1], dp[i, j - x]);
if (res < dp[i, j])
dp[i, j] = res;
}
}
}
return dp[2, n];
}
static void Main() {
int n = 100;
Console.WriteLine("Minimum number of drops for " + n + " floors is " + EggDrop(n));
}
}In this Python version, a dynamic programming approach is used to build a table of minimum trials required for each combination of eggs and floors. The nested loop iteratively fills this table by minimizing the maximum number of trials among all possible drop points.
Time Complexity: O(n²)
Space Complexity: O(n)
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
finj - 1floors, which requiresj - 1operations. Therefore, the total number of operations is1 + (j - 1); - The egg does not break. At this time, we have two eggs left and need to determine
fini - jfloors, which requiresf[i - j]operations. Therefore, the total number of operations is1 + 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.
function twoEggDrop(n: number): number {
const f: number[] = Array(n + 1).fill(Infinity);
f[0] = 0;
for (let i = 1; i <= n; ++i) {
for (let j = 1; j <= i; ++j) {
f[i] = Math.min(f[i], 1 + Math.max(j - 1, f[i - j]));
}
}
return f[n];
}func twoEggDrop(n int) int {
f := make([]int, n+1)
for i := range f {
f[i] = 1 << 29
}
f[0] = 0
for i := 1; i <= n; i++ {
for j := 1; j <= i; j++ {
f[i] = min(f[i], 1+max(j-1, f[i-j]))
}
}
return f[n]
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Iterative Strategy Using Triangular Numbers | Time Complexity: |
| Approach 2: Dynamic Programming | Time Complexity: |
| Dynamic Programming | – |
Complexity analysis
| 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. |
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.