Egg Drop With 2 Eggs and N Floors - Video Solutions

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.