Super Egg Drop: Flipping the DP Perspective

You have k identical eggs and a building with n floors. There is some critical floor f such that any egg dropped from a floor higher than f will break, and any egg dropped from floor f or below will survive. You need to find the minimum number of moves guaranteed to determine f, no matter its value. In each move, you pick a floor, drop an egg, and observe whether it breaks or survives.

This is LeetCode 887: Super Egg Drop, and it is one of the most famous DP problems because the obvious approach is too slow and the fast approach requires you to think about the problem backwards.

For k = 2 eggs and n = 6 floors, the answer is 3. You can always determine the critical floor in at most 3 drops, no matter where it is.

Why this problem matters

Super Egg Drop is a classic because it teaches you that the way you frame a DP problem can be the difference between a solution that passes and one that times out. Most DP problems let you define the state in the obvious way and grind through transitions. This one punishes you for that. The natural formulation leads to O(kn^2) time, which is too slow for the constraints (k up to 100, n up to 10,000). The fast solution requires flipping the question entirely.

The problem also connects several big ideas: binary search on the answer, mathematical recurrences that resemble combinatorial identities, and the general principle that sometimes computing the inverse function is easier than computing the function itself. Once you learn this reframing trick, you will recognize opportunities to apply it in other problems where the direct DP is too expensive.

If you have solved Coin Change or Burst Balloons, you already know how to fill DP tables. But those problems have natural state definitions that work well. Super Egg Drop forces you to abandon the natural state and find a better one.

The naive approach and why it fails

The first formulation most people reach is: define dp[k][n] as the minimum number of moves to determine the critical floor with k eggs and n floors. If you drop an egg from floor x:

• If it breaks, you have k - 1 eggs and need to search floors 1 through x - 1, which is dp[k-1][x-1] moves.
• If it survives, you have k eggs and need to search floors x + 1 through n, which is dp[k][n-x] moves.

Since you want a guarantee (worst case), you take the max of those two outcomes. And since you get to choose x, you minimize over all possible floors:

dp[k][n] = min over x from 1 to n of (max(dp[k-1][x-1], dp[k][n-x]) + 1)

This works, but it is O(kn^2). For every (k, n) pair, you try all n possible floors. You can optimize the inner loop with binary search (since one term increases and the other decreases as x grows), bringing it down to O(kn log n). That might pass with tight constants, but there is a cleaner O(k log n) approach that avoids the whole mess.

Flipping the question

Here is the key insight. Instead of asking "given k eggs and n floors, what is the minimum number of moves?", ask the inverse question: "given k eggs and t moves, what is the maximum number of floors I can check?"

Define f(t, k) as the maximum number of floors you can determine the critical floor for, using at most t moves and k eggs.

When you drop an egg from some floor:

• If it breaks: you have t - 1 moves and k - 1 eggs left, so you can check f(t-1, k-1) floors below the current one.
• If it survives: you have t - 1 moves and k eggs left, so you can check f(t-1, k) floors above the current one.
• Plus the current floor itself: the floor you just dropped from is also checked.

This gives the recurrence:

f(t, k) = f(t-1, k-1) + f(t-1, k) + 1

The base cases are f(0, k) = 0 (zero moves means zero floors) and f(t, 0) = 0 (zero eggs means zero floors, since you cannot risk any drops).

The answer to the original problem is the smallest t such that f(t, k) >= n.

Clean solution

def superEggDrop(k, n):
    dp = [0] * (k + 1)
    t = 0
    while dp[k] < n:
        t += 1
        for i in range(k, 0, -1):
            dp[i] = dp[i - 1] + dp[i] + 1
    return t

Why the recurrence works

The recurrence f(t, k) = f(t-1, k-1) + f(t-1, k) + 1 captures a clean partition of the floors. Picture yourself standing on some floor with t moves and k eggs. You drop an egg:

• If it breaks, you know the critical floor is somewhere in the f(t-1, k-1) floors below you. You have t-1 moves and k-1 eggs to narrow it down.
• If it survives, you know the critical floor is somewhere in the f(t-1, k) floors above you. You have t-1 moves and k eggs to narrow it down.
• The floor you dropped from is also resolved by this drop.

So the total floors you can handle is the sum of all three. There is no overlap and no gap. This is why the flipped formulation is so powerful: the subproblems partition perfectly, with no min or max over choices. The recurrence is a simple sum, and it builds up the answer in O(k) work per increment of t. Since t grows at most logarithmically in n (because f(t, k) grows at least exponentially when k is 2 or more), the total time is O(k * log n).

Notice how this recurrence looks like Pascal's triangle. That is not a coincidence. With k eggs and t moves, f(t, k) equals the sum of binomial coefficients C(t,1) + C(t,2) + ... + C(t,k). Each term corresponds to a specific "number of eggs that break" scenario, which is a combinatorial counting argument.

Complexity analysis

Time: O(k * log n). Each increment of t does O(k) work to update the 1D array. The loop runs until f(t, k) >= n, and since f(t, k) roughly doubles each time t increases (for k of 2 or more), the number of iterations is O(log n).

Space: O(k). You only need a single 1D array of length k + 1. Each step updates the array in reverse order (from k down to 1) to avoid overwriting values you still need, the same reverse-iteration trick from the 0/1 Knapsack pattern.

Edge cases to watch for

• k = 1: with a single egg, you must go floor by floor from the bottom. The answer is always n.
• n = 0: zero floors means zero moves. The answer is 0.
• n = 1: one floor always takes exactly 1 move, regardless of how many eggs you have.
• k at least n: when you have at least as many eggs as floors, you can always binary search, so the answer is ceil(log2(n + 1)).
• Very large n (up to 10,000) with small k: the O(k * log n) approach handles this easily. Even k = 100 and n = 10,000 finishes instantly.

The building blocks

This problem combines two reusable patterns:

Inverse DP (flip the question). When the direct DP formulation is expensive because of a min-max structure with a loop over choices, consider asking the inverse question. Instead of "what is the minimum cost for this target?", ask "what is the maximum target achievable with this budget?". The inverse often has a simpler recurrence. You will see this pattern in any problem where the direct formulation requires searching over a parameter that the inverse formulation naturally eliminates.

1D DP with reverse iteration. The solution uses a 1D array updated in reverse order, the same space-optimization trick that appears in knapsack-style problems. By iterating from k down to 1, each cell reads the old value of dp[i-1] (not yet overwritten in this round) and the old value of dp[i] (which was the value from the previous t). This avoids allocating a 2D table.

From understanding to recall

You have seen the naive O(kn^2) approach, understood why flipping the question leads to a cleaner recurrence, and traced through the table for a small example. But reproducing this under pressure is another matter entirely. The tricky part is not the recurrence itself. It is remembering to flip the question in the first place.

In an interview, you need to recognize that the direct DP has a costly inner loop, decide to invert the problem, define f(t, k) as the maximum floors, write the recurrence f(t-1, k-1) + f(t-1, k) + 1, implement the 1D array with reverse iteration, and loop until f(t, k) meets or exceeds n. That sequence of decisions needs to feel automatic, not improvised.

Spaced repetition helps you internalize the "flip the question" pattern so it surfaces naturally when you see a DP problem where the direct approach is too expensive. After a few reps, the moment you notice a min over max structure with a linear scan, your instinct will be to ask whether the inverse problem has a simpler recurrence.

Related posts

• Coin Change - Classic DP with a table-filling approach
• Burst Balloons - Another hard DP problem requiring a creative reframing
• Dungeon Game - DP where the direction of computation matters