LeetCode 887 - Super Egg Drop

LeetCode Problem 887

Difficulty: 🔴 Hard
Topics: Math, Binary Search, Dynamic Programming

Solution

Problem Understanding

The problem asks us to determine the minimum number of moves required to identify a critical floor in a building using a limited number of eggs.

We are given two integers:

• k, the number of identical eggs
• n, the number of floors in the building

There exists some unknown floor f such that:

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

Our task is to determine the exact value of f with certainty while minimizing the number of moves in the worst case.

A move consists of dropping an egg from a chosen floor. After the drop:

• If the egg breaks, it can no longer be used
• If it survives, it can still be reused

The key phrase is "with certainty." This means the strategy must work for every possible value of f from 0 to n.

The constraints are important:

• 1 <= k <= 100
• 1 <= n <= 10^4

A naive recursive search over all floors quickly becomes too slow because the number of states grows dramatically. Since n can be as large as 10,000, we need a highly optimized dynamic programming approach.

Several edge cases are especially important:

• When k = 1, we can only test floors sequentially from bottom to top
• When n = 1, the answer is always 1
• When there are many eggs relative to floors, the optimal strategy becomes very efficient
• Large values like k = 100 and n = 10000 require avoiding quadratic or cubic dynamic programming solutions

Approaches

Brute Force Dynamic Programming

A straightforward approach is to define:

dp(eggs, floors) = minimum number of moves needed with eggs eggs and floors floors.

For every possible floor x where we drop an egg:

• If the egg breaks, we must search below x, which gives:

dp(eggs - 1, x - 1)

• If the egg survives, we must search above x, which gives:

dp(eggs, floors - x)

Since we must guarantee correctness in the worst case, we take the maximum of the two outcomes:

1 + max(
    dp(eggs - 1, x - 1),
    dp(eggs, floors - x)
)

We then try every possible x from 1 to floors and choose the minimum result.

This recurrence is correct because every drop partitions the search space into two mutually exclusive possibilities. However, it is too slow because each state iterates across all floors, producing roughly O(k * n^2) complexity even with memoization.

For n = 10000, this becomes impractical.

Optimal Dynamic Programming by Moves

The key insight is to reverse the problem.

Instead of asking:

"What is the minimum number of moves needed for n floors?"

we ask:

"With m moves and k eggs, how many floors can we test?"

Define:

dp[m][k] = maximum number of floors that can be determined
           using m moves and k eggs

Suppose we drop an egg:

• If it breaks, we can test dp[m-1][k-1] floors below
• If it survives, we can test dp[m-1][k] floors above
• Plus the current floor itself

This gives the recurrence:

$dp[m][k] = dp[m-1][k-1] + dp[m-1][k] + 1$

This formulation is dramatically more efficient because the number of moves needed grows relatively slowly. We repeatedly increase the number of moves until the number of testable floors reaches or exceeds n.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(k * n²)	O(k * n)	Tries every drop floor for every state
Optimal	O(k * m)	O(k)	Uses move-based DP, where m is the answer

Since m is usually much smaller than n, the optimal approach is extremely fast in practice.

Algorithm Walkthrough

Optimal Dynamic Programming Algorithm

1. Create a one-dimensional DP array where dp[e] represents the maximum number of floors that can be tested using the current number of moves and e eggs.
2. Initialize all values to 0 because with zero moves we cannot determine any floors.
3. Start increasing the number of moves one by one.
4. For each move, update the DP array from right to left. Updating from right to left is important because each state depends on values from the previous move iteration.
5. Apply the recurrence:

$dp[e] = dp[e] + dp[e-1] + 1$

Here:

• dp[e] before update represents dp[m-1][e]
• dp[e-1] represents dp[m-1][e-1]
• +1 accounts for the current floor

6. After updating all egg counts for the current move, check whether dp[k] >= n.
7. Once dp[k] reaches or exceeds n, return the current number of moves.

Why it works

The recurrence correctly counts all floors we can distinguish after one additional move. A drop creates two subproblems:

• Below the drop floor if the egg breaks
• Above the drop floor if the egg survives

Since these regions are disjoint and the current floor itself is also tested, the total number of distinguishable floors is the sum of both regions plus one. By increasing moves incrementally, the first move count that covers at least n floors is guaranteed to be the minimum answer.

Python Solution

class Solution:
    def superEggDrop(self, k: int, n: int) -> int:
        dp = [0] * (k + 1)
        moves = 0

        while dp[k] < n:
            moves += 1

            for eggs in range(k, 0, -1):
                dp[eggs] = dp[eggs] + dp[eggs - 1] + 1

        return moves

The implementation uses a one-dimensional dynamic programming array to save space.

dp[eggs] stores the maximum number of floors that can currently be tested using a given number of eggs and the current move count.

The algorithm repeatedly increases the number of moves until the coverage becomes large enough to include all n floors.

The update loop runs backward because each state depends on the previous move's values. If we updated left to right, we would overwrite values needed later in the same iteration.

The recurrence:

$dp[e] = dp[e] + dp[e-1] + 1$

encodes the two possible outcomes of dropping an egg:

• Egg breaks, use one fewer egg
• Egg survives, keep same number of eggs

The algorithm stops immediately once enough floors can be tested.

Go Solution

func superEggDrop(k int, n int) int {
    dp := make([]int, k+1)
    moves := 0

    for dp[k] < n {
        moves++

        for eggs := k; eggs >= 1; eggs-- {
            dp[eggs] = dp[eggs] + dp[eggs-1] + 1
        }
    }

    return moves
}

The Go implementation mirrors the Python logic closely.

Slices are used instead of Python lists. Since Go integers are fixed-width, it is worth noting that the values remain safely within range for the given constraints.

The backward iteration order is equally important in Go because the recurrence depends on values from the previous iteration state.

Worked Examples

Example 1

Input:

k = 1, n = 2

Initial state:

Moves	dp[1]	Floors Testable
0	0	0

After move 1:

dp[1] = 0 + 0 + 1 = 1

Moves	dp[1]	Floors Testable
1	1	1

Still less than 2.

After move 2:

dp[1] = 1 + 0 + 1 = 2

Moves	dp[1]	Floors Testable
2	2	2

Now dp[1] >= 2, so answer is 2.

Example 2

Input:

k = 2, n = 6

Initial:

Moves	dp[1]	dp[2]
0	0	0

After move 1:

Calculation	Result
dp[2] = 0 + 0 + 1	1
dp[1] = 0 + 0 + 1	1

State:

Moves	dp[1]	dp[2]
1	1	1

After move 2:

Calculation	Result
dp[2] = 1 + 1 + 1	3
dp[1] = 1 + 0 + 1	2

State:

Moves	dp[1]	dp[2]
2	2	3

After move 3:

Calculation	Result
dp[2] = 3 + 2 + 1	6
dp[1] = 2 + 0 + 1	3

State:

Moves	dp[1]	dp[2]
3	3	6

Now dp[2] >= 6, so answer is 3.

Example 3

Input:

k = 3, n = 14

Progression:

Moves	dp[1]	dp[2]	dp[3]
0	0	0	0
1	1	1	1
2	2	3	3
3	3	6	7
4	4	10	14

At move 4, we can test 14 floors, so answer is 4.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(k * m)	m moves, each updating k eggs
Space	O(k)	One DP array of size k + 1

The number of moves m is the minimum answer returned by the algorithm. In practice, m grows much slower than n, making this solution extremely efficient even for large buildings.

The space optimization works because each DP state only depends on the previous move's values, allowing compression into a single array.

Test Cases

solution = Solution()

assert solution.superEggDrop(1, 2) == 2  # Single egg, must check sequentially
assert solution.superEggDrop(2, 6) == 3  # Standard example
assert solution.superEggDrop(3, 14) == 4  # Standard example

assert solution.superEggDrop(1, 1) == 1  # Smallest non-zero building
assert solution.superEggDrop(2, 1) == 1  # Only one floor
assert solution.superEggDrop(100, 1) == 1  # Many eggs, trivial floors

assert solution.superEggDrop(2, 2) == 2  # Two floors with two eggs
assert solution.superEggDrop(2, 3) == 2  # Binary-style improvement
assert solution.superEggDrop(2, 100) == 14  # Classic triangular number case

assert solution.superEggDrop(3, 25) == 5  # Moderate-sized input
assert solution.superEggDrop(4, 500) == 11  # Larger DP coverage
assert solution.superEggDrop(100, 10000) == 14  # Stress test with many eggs

Test Case Summary

Test	Why
k=1, n=2	Validates sequential search behavior
k=2, n=6	Standard balanced example
k=3, n=14	Demonstrates rapid DP growth
k=1, n=1	Smallest valid input
k=100, n=1	Many eggs but trivial floors
k=2, n=2	Small balanced configuration
k=2, n=100	Tests classic triangular progression
k=100, n=10000	Stress test for performance

Edge Cases

Single Egg

When only one egg is available, the algorithm cannot use divide-and-conquer style strategies because breaking the egg ends all future testing. The only safe approach is linear search from the bottom upward.

This case is a common source of incorrect optimizations. The DP formulation handles it naturally because:

$dp[m][1] = m$

meaning one egg and m moves can test exactly m floors.

Very Small Number of Floors

Cases like n = 1 or n = 2 are easy to mishandle with off-by-one errors. Some implementations accidentally return zero moves for one floor or overcount moves when initializing DP states.

This implementation avoids those issues because the DP starts at zero coverage and increments only after performing a move.

Large Egg Count

When k is much larger than needed, some recursive approaches waste enormous amounts of computation exploring redundant states.

The move-based DP remains efficient because it only tracks how many floors can be covered after each move. Even with k = 100, the answer for n = 10000 is very small, so the algorithm finishes quickly.

In-Place DP Updates

Updating the DP array from left to right would corrupt values needed later in the same iteration. This is a subtle bug that produces incorrect results.

The implementation updates from right to left specifically to preserve the previous move's states during computation.