Super Egg Drop: The DP-Inversion Trick That Kills the O(kn²) Table
Super Egg Drop solved by flipping the question to max floors per move — a worked 2-eggs-6-floors trace, JavaScript code, and the O(k log n) complexity.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Super Egg Drop is the problem that punishes brute force the hardest. The natural DP — "minimum moves to search n floors with k eggs" — is correct, runs in O(kn²), and times out the moment n climbs past a few thousand.
The trick that turns it into a handful of lines is to invert the question. Instead of asking how many moves do n floors need, ask how many floors can m moves cover. That single reframe collapses a two-dimensional search into a running counter that stops the instant it clears n.
This guide teaches the exact algorithm the Super Egg Drop visualizer animates, variable names and all.
The problem
You have k identical eggs and a building with n floors numbered 1 to n. There is a hidden critical floor f (where 0 ≤ f ≤ n): an egg dropped from any floor above f breaks; an egg dropped from floor f or below survives and can be reused. A broken egg is gone for good.
Return the minimum number of drops that guarantees you can identify f in the worst case — no luck allowed, the answer must hold against the most adversarial placement of f.
Input: k = 2 eggs, n = 6 floors
Output: 3
With only 2 eggs you cannot binary-search safely: if the first egg
breaks you must scan the floors below it one at a time. The optimal
strategy guarantees the answer in 3 drops no matter where f sits.The worst-case constraint is the whole difficulty. With one egg you have no choice but to test floors 1, 2, 3, … in order — dropping from floor 50 risks breaking your only egg and learning nothing about floors 1–49. More eggs buy you the freedom to skip ahead.
The brute force baseline
The textbook DP defines dp(eggs, floors) = minimum drops to find f among floors floors using eggs eggs. You try dropping from every floor x, and each choice splits into two futures:
function superEggDrop(k, n) {
const memo = new Map();
function dp(eggs, floors) {
if (floors === 0) return 0; // nothing left to find
if (eggs === 1) return floors; // must scan linearly
const key = eggs + ',' + floors;
if (memo.has(key)) return memo.get(key);
let best = Infinity;
for (let x = 1; x <= floors; x++) {
const broke = dp(eggs - 1, x - 1); // search below x
const survived = dp(eggs, floors - x); // search above x
best = Math.min(best, 1 + Math.max(broke, survived));
}
memo.set(key, best);
return best;
}
return dp(k, n);
}It is correct, but look at the inner loop. There are k · n states, and filling each one scans up to n candidate floors — O(kn²) total. For n = 10⁴ that is a billion operations per egg. The max is there because the adversary picks the worse branch, and the min is you choosing the drop floor that makes that worst case as small as possible.
The key insight: count floors, not moves
Flip the dimensions. Define dp[i] = the maximum number of floors you can fully resolve with i eggs and m moves. Start at m = 0 and increment m one move at a time, updating every dp[i] until dp[k] finally reaches n. The number of moves it took is the answer.
Why does one move let you cover dp[i] + dp[i-1] + 1 floors? When you drop an egg with i eggs and m moves in hand:
- It breaks. You drop to
i-1eggs andm-1moves, so you can resolvedp[i-1]floors below the drop point. - It survives. You keep
ieggs but spend a move, so you can resolvedp[i](the previous move's value) floors above. - The tested floor itself counts as
+1.
So the recurrence is dp[i] = dp[i] + dp[i-1] + 1, where both right-hand terms are the previous move's values. This is the DP inversion: floors grow at least exponentially with moves, so m reaches n in O(k log n) iterations instead of O(kn²).
The optimal solution
This is the exact code from components/visualize/dp/super-egg-drop.tsx. A single 1D array, updated in place:
var superEggDrop = function(k, n) {
let dp = new Array(k + 1).fill(0);
let moves = 0;
while (dp[k] < n) {
moves++;
for (let i = k; i >= 1; i--) {
dp[i] = 1 + dp[i] + dp[i - 1];
}
}
return moves;
};The descending loop (i from k down to 1) is load-bearing, not stylistic. When you update dp[i], you read dp[i-1] — and you need it to still hold the previous move's value. Iterating downward guarantees dp[i-1] hasn't been touched yet this move. Reverse the loop and every dp[i-1] would already be overwritten, quietly computing the wrong recurrence.
Walkthrough
Tracing superEggDrop(2, 6). The array is [dp[0], dp[1], dp[2]]; dp[0] stays 0 forever (zero eggs resolve zero floors). We stop when dp[2] ≥ 6.
| Move | i | dp[i] = 1 + dp[i] + dp[i-1] | dp after step | dp[2] vs 6 |
|---|---|---|---|---|
| — | — | init | [0, 0, 0] | 0 < 6, loop |
| 1 | 2 | 1 + 0 + 0 = 1 | [0, 0, 1] | — |
| 1 | 1 | 1 + 0 + 0 = 1 | [0, 1, 1] | 1 < 6, loop |
| 2 | 2 | 1 + 1 + 1 = 3 | [0, 1, 3] | — |
| 2 | 1 | 1 + 1 + 0 = 2 | [0, 2, 3] | 3 < 6, loop |
| 3 | 2 | 1 + 3 + 2 = 6 | [0, 2, 6] | — |
| 3 | 1 | 1 + 2 + 0 = 3 | [0, 3, 6] | 6 ≥ 6, stop |
After move 3, dp[2] = 6, which covers all six floors, so the loop exits and returns moves = 3. Notice how dp[2] grows 1 → 3 → 6: with two eggs the reachable floors follow the triangular numbers m(m+1)/2, exactly why 3 moves cover 6 floors but 2 moves only cover 3.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Brute-force DP | O(k·n²) | O(k·n) | k·n states, each scanning up to n drop floors |
| DP inversion | O(k · log n) | O(k) | m reaches n in ~log n moves; each move does k updates |
Space is a single array of k + 1 integers. The number of while iterations is the answer m itself, and since coverage grows super-linearly with m, m is bounded by O(log n) for any fixed k — that is the entire win.
Common mistakes
- Reversing the inner loop. Iterating
ifrom1up tokoverwritesdp[i-1]beforedp[i]reads it, so both terms come from the current move instead of the previous one. The answer comes out too small. - Forgetting
dp[0]stays zero. With zero eggs you can resolve zero floors. It anchors the break branch of the recurrence; drop it anddp[1]inflates. - Assuming binary search is optimal. Halving works only with unlimited eggs. With 2 eggs and 100 floors the answer is 14, not 7 — a broken first egg forces a linear scan of everything below it.
- Confusing floors with moves. The array stores floors coverable, and the loop counter stores moves spent. The answer is the counter, not any cell of the array.
Where this pattern shows up next
DP inversion — redefining the DP so the answer becomes a threshold you grow toward — and general 1D bottom-up tabulation carry into plenty of neighbours:
- Word Break — boolean DP over string prefixes, another "fill until a target index is reachable" shape.
- Longest Increasing Subsequence — the patience-sorting version trades an O(n²) table for an O(n log n) search, the same "collapse a dimension" instinct.
- Partition Equal Subset Sum — a 1D array updated in a deliberate direction so each item is used once, exactly like the descending loop here.
- Coin Change II — counting DP where the update order decides whether combinations or permutations get counted.
You can also step through Super Egg Drop interactively and watch the DP table fill row by row as each move extends the coverage.
FAQ
Why is binary search not the answer to Super Egg Drop?
Binary search assumes you can always afford to probe the middle. That only holds with unlimited eggs. When eggs are scarce, breaking one at floor n/2 may leave you unable to test the floors below it safely, forcing a linear scan. The DP-inversion recurrence prices in exactly how much a broken egg costs, which is why 2 eggs over 100 floors need 14 drops rather than the 7 a pure binary search suggests.
What does dp[i] actually represent in the optimal solution?
dp[i] is the maximum number of floors you can fully resolve using i eggs within the current number of moves. It is the inverse of the naive formulation, which stored moves indexed by floors. By counting floors instead, the outer while loop just increments moves until dp[k] reaches n, and the answer is the move count — no two-dimensional table required.
Why must the inner loop count down from k to 1?
Each update dp[i] = 1 + dp[i] + dp[i-1] needs both dp[i] and dp[i-1] to reflect the previous move. Counting down guarantees dp[i-1] is still untouched when dp[i] reads it. If you looped upward, dp[i-1] would already carry this move's new value, silently corrupting the recurrence and returning too few moves.
What is the time complexity, and why is it so much faster?
O(k · log n) time and O(k) space. Coverage grows super-linearly with moves — with k eggs it grows like a degree-k polynomial in m — so the number of moves needed to reach n floors is only about O(log n). Each move performs k array updates, giving O(k log n) total. The brute-force DP is O(kn²) because it scans every possible drop floor for every state.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.