#1884

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Egg Drop With 2 Eggs and N Floors

Determine the minimum drops needed to find the critical floor using 2 eggs with optimized state transition dynamic programming.

math dynamic programming

Problem Statement

You have a building with n floors labeled from 1 to n and exactly two identical eggs. There exists a floor f such that any egg dropped above f will break and any egg dropped at or below f will survive. You must determine the value of f using the minimum number of drops.

Each move allows dropping an unbroken egg from any floor. If the egg breaks, it cannot be reused; if it survives, it can be dropped again. Your goal is to compute the minimum number of drops required in the worst case to identify the critical floor f.

Examples

Example 1

Input: n = 2

Output: 2

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

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

Solution Approach

Mathematical Observation

Recognize that using 2 eggs, the optimal strategy does not always drop the first egg from the middle floor. Instead, choose floors so that each potential drop balances the remaining attempts. This reduces the maximum number of drops in the worst case.

Dynamic Programming Formulation

Define dp[eggs][floors] as the minimum number of moves needed. For 2 eggs, compute dp[2][n] by considering dropping an egg from floor x: if it breaks, use dp[1][x-1]; if it survives, use dp[2][n-x]. Take the minimum of max(break, survive) across all x.

Optimized State Transition

Use the triangular number approach: drop the first egg at increasing floors that decrease the remaining attempts by 1 each time. This ensures that the sum of possible remaining drops covers all floors, achieving minimal worst-case drops efficiently.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n^2) for naive DP but can be optimized to O(n) using triangular number method. Space complexity is O(n) when storing only current egg states instead of full DP table.

What Interviewers Usually Probe

Asks if dropping from the middle floor is always optimal for two eggs.
Mentions worst-case scenario and minimizing maximum drops.
Checks understanding of state transition DP and triangular number optimization.

Common Pitfalls or Variants

Common pitfalls

Assuming binary search works with only 2 eggs, which can exceed allowed drops.
Failing to balance drops properly, leading to suboptimal worst-case attempts.
Overcomplicating DP by storing unnecessary states instead of optimizing transitions.

Follow-up variants

Egg Drop with k eggs and n floors using full DP table.
Determine minimum drops with 2 eggs and specific floor constraints.
Compute drops when eggs have a probability of breaking instead of deterministic behavior.

FAQ

What is the main strategy for Egg Drop With 2 Eggs and N Floors?

Use state transition dynamic programming to select floors that balance remaining attempts, reducing maximum drops.

Can we apply binary search directly with 2 eggs?

No, binary search can fail in worst case because breaking the first egg too early increases total drops.

How does triangular number optimization help?

It ensures each drop reduces remaining potential floors optimally, achieving minimal worst-case attempts.

What is the time complexity for this problem?

Naive DP is O(n^2), but using the triangular number approach reduces it to O(n).

Does GhostInterview show step-by-step drops for n floors?

Yes, it calculates each floor to drop from and tracks outcomes to explain the minimal moves strategy.

terminal

Solution

Solution 1: 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]$.

1

2

3

4

5

6

7

class Solution:
    def twoEggDrop(self, n: int) -> int:
        f = [0] + [inf] * n
        for i in range(1, n + 1):
            for j in range(1, i + 1):
                f[i] = min(f[i], 1 + max(j - 1, f[i - j]))
        return f[n]

Continue Practicing

#1872 stone game viii #1896 minimum cost to change the final value of expression #1866 number of ways to rearrange sticks with k sticks visible