LeetCode Problem 1884

Difficulty: 🟡 Medium
Topics: Math, Dynamic Programming

Solution

LeetCode 1884 - Egg Drop With 2 Eggs and N Floors

Problem Understanding

This problem asks us to determine the minimum number of moves required to identify a critical floor f in a building with n floors, using exactly two eggs.

The critical floor f has the following meaning:

• Any egg dropped from a floor higher than f will break.
• Any egg dropped from floor f or lower will survive.

The value of f can range from 0 to n.

If f = 0, eggs break from every floor.

If f = n, eggs never break.

We need to design a strategy that guarantees we can determine the exact value of f, regardless of what the actual answer is. The important part is that we are minimizing the worst case number of moves.

The input is a single integer n, representing the number of floors in the building. The output is the smallest number of moves needed to guarantee success.

The constraints are relatively small:

• 1 <= n <= 1000

This tells us that even quadratic dynamic programming solutions are feasible. However, there is also a much cleaner mathematical observation that leads to an optimal linear time solution.

The key difficulty comes from the fact that we only have two eggs. Once one egg breaks, we lose the ability to make risky jumps. With only one egg left, the only safe strategy is linear search.

Several edge cases are important:

• n = 1, only one floor exists, so exactly one move is needed.
• Small values like n = 2 or n = 3, where naive strategies can accidentally overestimate or underestimate the answer.
• Large values like n = 1000, where inefficient recursive solutions may become too slow.
• Situations where the first egg breaks early, forcing the second egg into a sequential search.

Approaches

Brute Force Dynamic Programming

A straightforward approach uses dynamic programming.

Define dp[i] as the minimum number of moves needed for i floors using two eggs.

For every possible first drop floor x:

• If the egg breaks, we must linearly search floors below x, requiring x - 1 additional moves.
• If the egg survives, we still need to solve the remaining i - x floors with two eggs.

The worst case for dropping at floor x is:

$1 + \max(x-1, dp[i-x])$

We try all x values and choose the minimum.

This gives the correct result because it explicitly evaluates every possible first move and accounts for the worst case outcome.

However, the time complexity becomes quadratic because for every floor count i, we test every possible dropping floor.

Optimal Mathematical Observation

The optimal solution comes from balancing the two possible outcomes.

Suppose we can make at most k moves.

If we drop the first egg from floor k:

• If it breaks, we can test floors below sequentially using the second egg, requiring at most k - 1 more moves.
• If it survives, we still have k - 1 moves left.

The next jump should therefore be smaller by one floor:

• First jump: k
• Second jump: k - 1
• Third jump: k - 2

And so on.

After k moves, the total number of floors we can cover is:

$1 + 2 + 3 + \cdots + k = \frac{k(k+1)}{2}$

We simply need the smallest k such that:

$\frac{k(k+1)}{2} \ge n$

This converts the problem into finding the smallest triangular number greater than or equal to n.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force DP	O(n²)	O(n)	Tries every possible first drop floor
Optimal Mathematical	O(√n)	O(1)	Uses triangular number observation

Algorithm Walkthrough

1. Initialize two variables:

• moves = 0
• floorsCovered = 0

2. Each move increases the number of floors we can guarantee testing.

On the first move we can cover 1 floor.

On the second move we can cover 2 additional floors.

On the third move we can cover 3 additional floors. 3. Repeatedly increase the move count:

• Increment moves
• Add moves to floorsCovered

4. Continue until floorsCovered >= n.
5. Return moves.

For example, if n = 100:

• After 1 move: 1 floor
• After 2 moves: 3 floors
• After 3 moves: 6 floors
• ...
• After 14 moves: 105 floors

Since 105 is the first triangular number at least 100, the answer is 14.

Why it works

The strategy works because each drop must account for both outcomes:

• Egg breaks
• Egg survives

By decreasing the jump size by one each time, we guarantee that no matter when the first egg breaks, the remaining floors can still be checked sequentially with the remaining moves.

The triangular number formula exactly represents the maximum number of floors that can be safely covered with k moves and two eggs.

Python Solution

class Solution:
    def twoEggDrop(self, n: int) -> int:
        moves = 0
        floors_covered = 0

        while floors_covered < n:
            moves += 1
            floors_covered += moves

        return moves

The implementation directly follows the mathematical observation.

The variable moves represents the number of allowed drops. The variable floors_covered stores the maximum number of floors we can determine using that many moves.

Each iteration adds one more move and expands the coverage by the size of the new jump.

Once the covered floors become at least n, we know the current number of moves is sufficient.

Because triangular numbers grow quadratically, the loop runs only about √n times.

Go Solution

func twoEggDrop(n int) int {
    moves := 0
    floorsCovered := 0

    for floorsCovered < n {
        moves++
        floorsCovered += moves
    }

    return moves
}

The Go implementation is nearly identical to the Python version.

Go uses explicit variable declarations with :=. Since n <= 1000, integer overflow is not a concern. No slices or dynamic memory are needed because the solution uses only constant extra space.

Worked Examples

Example 1

Input:

n = 2

We compute triangular numbers until coverage reaches 2.

Moves	Floors Covered
1	1
2	3

At 2 moves, we can cover at least 2 floors.

Answer:

2

Example 2

Input:

n = 100

Moves	Floors Covered
1	1
2	3
3	6
4	10
5	15
6	21
7	28
8	36
9	45
10	55
11	66
12	78
13	91
14	105

The first coverage value at least 100 is 105.

Answer:

14

Example 3

Input:

n = 1

Moves	Floors Covered
1	1

Answer:

1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(√n)	Triangular numbers grow quadratically
Space	O(1)	Only a few integer variables are used

The loop continues until:

$\frac{k(k+1)}{2} \ge n$

Solving approximately gives:

$k \approx \sqrt{2n}$

Therefore the number of iterations is proportional to √n.

Test Cases

sol = Solution()

assert sol.twoEggDrop(1) == 1  # minimum possible input
assert sol.twoEggDrop(2) == 2  # small example from problem
assert sol.twoEggDrop(3) == 2  # triangular number boundary
assert sol.twoEggDrop(4) == 3  # requires another move
assert sol.twoEggDrop(6) == 3  # exact triangular number
assert sol.twoEggDrop(7) == 4  # just above triangular number
assert sol.twoEggDrop(10) == 4  # another triangular number
assert sol.twoEggDrop(11) == 5  # just above triangular number
assert sol.twoEggDrop(100) == 14  # provided example
assert sol.twoEggDrop(1000) == 45  # upper constraint stress test

Test Summary

Test	Why
n = 1	Smallest valid input
n = 2	Basic example
n = 3	Exact triangular number
n = 4	Requires next move after triangular boundary
n = 6	Another exact triangular number
n = 7	Tests transition between move counts
n = 10	Larger triangular number
n = 11	Just above triangular threshold
n = 100	Provided example
n = 1000	Maximum constraint stress test

Edge Cases

One important edge case is when n = 1. With only one floor, the answer must be exactly one move. Some implementations accidentally return zero because they initialize incorrectly or use the wrong loop condition. Our implementation handles this correctly because the loop executes once and immediately reaches sufficient coverage.

Another important edge case occurs when n is exactly a triangular number, such as 3, 6, or 10. In these situations, the optimal number of moves lands precisely on the boundary. Off by one errors are common here. Our implementation uses while floors_covered < n, ensuring we stop immediately when coverage becomes equal to n.

A third important case occurs when n is just above a triangular number, such as 7 or 11. These values require one additional move even though the previous triangular number is very close. Incorrect implementations sometimes underestimate the required moves. Since we continue iterating until coverage is at least n, these cases are handled correctly.

Finally, large inputs such as n = 1000 validate that the implementation remains efficient. Recursive or quadratic approaches may still work for this constraint, but the mathematical solution stays extremely fast and uses constant memory.