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.

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

python

▶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

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.

06

Complexity

Time

O(k · answer)

Space

O(k)

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