LeetCode 887: Super Egg Drop

Problem Restatement

We are given k identical eggs and a building with n floors.

There is some unknown floor f such that:

We need to determine the exact value of f.

Each move lets us drop one unbroken egg from any floor. If the egg breaks, it cannot be used again. If it does not break, we can reuse it.

Return the minimum number of moves needed to determine f with certainty in the worst case.

LeetCode gives constraints 1 <= k <= 100 and 1 <= n <= 10^4.

Input and Output

Function shape:

def superEggDrop(self, k: int, n: int) -> int:
    ...

Examples

Example 1:

Input: k = 1, n = 2
Output: 2

With only one egg, we must test floors from bottom to top.

Drop from floor 1.

If it breaks, then f = 0.

If it survives, drop from floor 2.

So we need 2 moves in the worst case.

Example 2:

Input: k = 2, n = 6
Output: 3

With two eggs and six floors, three moves are enough.

One possible strategy is to drop from floor 3.

If it breaks, use one egg to test floors 1 and 2.

If it survives, test higher floors with the remaining moves.

Example 3:

Input: k = 3, n = 14
Output: 4

With three eggs and fourteen floors, four moves are enough.

First Thought: Try Every First Drop Floor

A direct dynamic programming definition is:

dp[eggs][floors] = minimum moves needed

Suppose we choose a first drop floor x.

There are two cases.

If the egg breaks, then we have:

eggs - 1 eggs
x - 1 lower floors to check

If the egg does not break, then we have:

eggs eggs
floors - x higher floors to check

Since we need a worst-case guarantee, the cost of dropping at floor x is:

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

Then we minimize this over all possible x.

This is correct, but it is too slow if implemented directly, because each state tries many drop floors.

Problem With the Direct DP

There are roughly:

k * n

states.

For each state, trying every first drop floor may cost up to:

n

So the direct version can take:

O(k * n^2)

With n = 10^4, this is too large.

We need a better DP viewpoint.

Key Insight

Instead of asking:

How many moves do we need for n floors?

ask the reverse question:

How many floors can we determine with m moves and k eggs?

Define:

dp[eggs][moves] = maximum number of floors we can check with this many eggs and moves

Now consider one drop.

If the egg breaks, we can check floors below the drop using:

eggs - 1 eggs
moves - 1 moves

That covers:

dp[eggs - 1][moves - 1]

floors below.

If the egg does not break, we can check floors above the drop using:

eggs eggs
moves - 1 moves

That covers:

dp[eggs][moves - 1]

floors above.

The current drop floor itself accounts for 1 more floor.

So:

dp[eggs][moves]
=
dp[eggs - 1][moves - 1]
+ 1
+ dp[eggs][moves - 1]

We keep increasing moves until:

dp[k][moves] >= n

The first such moves is the answer.

Algorithm

Use a one-dimensional DP array:

dp[eggs]

where dp[eggs] means the maximum number of floors that can be checked with the current number of moves and eggs eggs.

Initialize all values to 0.

Then repeat:

1. Increase moves by 1.
2. Update eggs from k down to 1.
3. Apply the recurrence:

dp[eggs] = dp[eggs] + dp[eggs - 1] + 1

The reverse loop is important because dp[eggs - 1] must still mean the value from the previous move count.

Stop when:

dp[k] >= n

Return moves.

Walkthrough

Use:

k = 2
n = 6

Start:

dp = [0, 0, 0]
moves = 0

After 1 move:

After 2 moves:

After 3 moves:

Now dp[2] = 6, so with 2 eggs and 3 moves we can determine f among 6 floors.

Answer:

3

Correctness

Let dp[e] after m iterations mean the maximum number of floors whose critical floor can be determined using e eggs and at most m moves.

For m = 0, no moves are available, so zero floors can be checked. The initialization is correct.

Now suppose the interpretation is true for m - 1 moves.

With e eggs and m moves, choose one floor to drop from.

If the egg breaks, then we have e - 1 eggs and m - 1 moves left. By the induction hypothesis, we can handle dp[e - 1] floors below the chosen floor.

If the egg survives, then we still have e eggs and m - 1 moves left. By the induction hypothesis, we can handle dp[e] floors above the chosen floor.

The chosen floor itself adds one more distinguishable floor.

Therefore, with e eggs and m moves, we can handle:

previous_dp[e - 1] + 1 + previous_dp[e]

floors.

This is exactly the update rule.

The algorithm stops at the first moves such that dp[k] >= n. At that point, moves moves are enough to determine the critical floor among n floors. Since we increase moves one at a time and stop at the first sufficient value, this number is minimal.

Thus, the algorithm returns the correct minimum worst-case number of moves.

Complexity

Since n <= 10^4, the number of moves is small enough for this method.

Implementation

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

Code Explanation

We create a DP array:

dp = [0] * (k + 1)

dp[eggs] means how many floors we can check with the current number of moves and eggs eggs.

The loop continues until we can cover all n floors:

while dp[k] < n:

Each loop adds one allowed move:

moves += 1

Then we update egg counts in reverse:

for eggs in range(k, 0, -1):

The recurrence is:

dp[eggs] = dp[eggs] + dp[eggs - 1] + 1

Here:

When dp[k] reaches at least n, the current moves is enough.

Testing

def run_tests():
    s = Solution()

    assert s.superEggDrop(1, 2) == 2
    assert s.superEggDrop(2, 6) == 3
    assert s.superEggDrop(3, 14) == 4
    assert s.superEggDrop(1, 10) == 10
    assert s.superEggDrop(2, 100) == 14
    assert s.superEggDrop(100, 1) == 1

    print("all tests passed")

run_tests()

Test meaning: