LeetCode #887 Hard

Super Egg Drop

With k eggs and n floors, find the minimum number of moves that guarantees locating the critical floor.

dpmathbinary-search

02

Intuition

Flip the question: instead of “how many moves for n floors?”, ask “how many floors can m moves and k eggs cover?” One drop splits the world: if the egg breaks you have m−1 moves and k−1 eggs for the floors below; if it survives, m−1 moves and k eggs for the floors above. So f(m,k) = f(m−1,k−1) + f(m−1,k) + 1 — and the answer is the smallest m with coverage ≥ n.

How to spot this pattern

The state inversion that makes this tractable: instead of asking "how many moves for n floors?", ask "how many floors can I cover with e eggs and m moves?" That flips an expensive minimisation into a simple additive recurrence — dp[e] += dp[e-1] + 1 — and you increment moves until coverage reaches n. When a DP is too slow, try swapping an answer with a parameter.

03

Approach

1

Why the naive DP is slow

dp[k][n] = 1 + min over pivot x of max(dp[k−1][x−1], dp[k][n−x]) is O(k·n²) — too slow for n up to 10⁴ without a monotonic/binary-search optimization.

2

Invert to coverage

f(m,k): max floors decidable in m moves with k eggs. The drop floor contributes 1, breaks send you down (f(m−1,k−1) floors), survives send you up (f(m−1,k) floors). Sum them.

3

March m upward

Keep a 1-D array over eggs, incrementing m until f(m,k) ≥ n. Coverage grows fast (binomial sums — nearly exponential in m), so m stays small.

04

Solution & live demo

▶1class Solution:
▶2    def superEggDrop(self, k, n):
▶3        # dp[e] = max floors coverable with e eggs and m moves
▶4        dp = [0] * (k + 1)
▶5        m = 0
▶6        while dp[k] < n:
▶7            m += 1
▶8            for e in range(k, 0, -1):       # descend so dp[e-1] is previous m
▶9                dp[e] = dp[e] + dp[e - 1] + 1
▶10        return m

05

Common pitfalls

Modelling it as a minimisation over drop floors

✗ Wrong

dp[e][n] = 1 + min(max(dp[e-1][x-1], dp[e][n-x])
                   for x in range(1, n + 1))

✓ Right

while dp[k] < n:
    m += 1
    for e in range(k, 0, -1):
        dp[e] = dp[e] + dp[e - 1] + 1

The direct formulation is O(k·n²) and times out for n = 10,000. Inverting the state — floors covered as a function of moves — makes each step O(k) with no inner search at all.

Iterating eggs in ascending order

✗ Wrong

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

✓ Right

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

dp[e-1] must hold the value from the previous move count. Ascending order overwrites it first, so the recurrence reads a value from the current round and overcounts — the same rolling-array hazard as 0/1 knapsack.

Returning the coverage instead of the move count

✗ Wrong

return dp[k]

✓ Right

return m

dp[k] is how many floors are now coverable, which is at least n. The question asks for the number of moves it took to get there.

06

Edge cases

k = 1

Must scan bottom-up: coverage grows by 1 per move — answer n.

n = 1

One drop decides — answer 1.

Many eggs

With k ≥ log₂n eggs it degenerates to binary search: ⌈log₂(n+1)⌉ moves.

07

Complexity

Time

O(k · answer)

Space

O(k)

answer ≤ n, and in practice ~n^(1/k); far below the O(k·n²) naive DP.