Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
With k eggs and n floors, find the minimum number of drops that guarantees you locate the critical floor in the WORST case. The classic 2-D DP is dp[e][f] = 1 + min over drop floor x of max(dp[e-1][x-1] (egg breaks), dp[e][f-x] (egg survives)) — O(k·n²). The slicker formulation flips it: dp[e][t] = max floors solvable with e eggs and t trials = dp[e-1][t-1] + dp[e][t-1] + 1, and you increase t until dp[k][t] ≥ n — O(k·n) (often O(k·log n) trials).
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you model worst-case search as a minimax DP, correctly handle the break-vs-survive split, and — at the hard bar — flip the state to 'floors per trial' for the fast solution.
Where candidates slip
Taking min (or average) instead of max over the two outcomes (you must survive the worst case), or mishandling the one-egg base case by trying to binary search with a single egg.
How to stand out
State the minimax clearly: 'I pick the floor to minimize, nature picks break-or-survive to maximize.' Give the classic dp[e][f], note it's O(k·n²) with a binary-search speedup, then present the dp[e][t] flip for O(k·n).
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewMin worst-case drops, k eggs n floorsEggs unlimited (k ≥ log₂ n)?YesNo, limited eggsExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 3
Brute Force — Recursive Minimax Over the Drop Floor
1Hint 1Explore hintHide hint
Suppose you drop an egg from some floor x (1 ≤ x ≤ f). Two things can happen, and you must be ready for the WORSE one. What are the two resulting subproblems?
2Hint 2Explore hintHide hint
If it breaks: you have e-1 eggs and only the x-1 floors below to search. If it survives: you still have e eggs and the f-x floors above. The cost of choosing x is 1 + max(those two), because the worst case decides.
3Hint 3Explore hintHide hint
You get to pick x, so minimize over it: drop(e, f) = 1 + min over x of max(drop(e-1, x-1), drop(e, f-x)). Base: drop(e,0)=0, drop(1,f)=f.
A · Core idea
Let drop(e, f) be the minimum worst-case drops with e eggs and f floors still in play. You choose a drop floor x. Nature then reveals one of two outcomes, and you must survive the worse one:
- The egg breaks. The critical floor is somewhere in
1..x-1, you've spent an egg, so the remaining subproblem isdrop(e-1, x-1). - The egg survives. The critical floor is in
x+1..f(a block off-xfloors), and you keep the egg:drop(e, f-x).
Because you don't control which happens, the cost of picking x is 1 + max(drop(e-1, x-1), drop(e, f-x)). Since you do control x, you minimize over all floors: drop(e, f) = 1 + min over x of max(...). That nested min of a max is the signature of a minimax.
The mental shift: you minimize, the adversary maximizes. Every drop floor x is a gamble whose downside is the worse of two futures. You can't wish away the bad branch — a guaranteed strategy must handle it — so you take the max of the two outcomes. Then, across all floors you could have chosen, you keep the one whose worst case is smallest. Confusing this with a plain min (assuming the lucky outcome) is the single most common error.
Why the break branch loses an egg and the survive branch doesn't. A broken egg is gone; a survivor is reusable. That asymmetry is the entire reason eggs are a scarce resource and the problem isn't just binary search.
Why `drop(1, f) = f`. With one egg you can't afford a break above the current floor — you'd have nothing left to localize f. So you must climb from floor 1 upward, costing f in the worst case. This base case quietly encodes 'no binary search with a single egg'.
Why we don't ship this. The same (e, f) state recurs through countless drop sequences — exponential overlap. Cache drop(e, f) and it collapses to a polynomial DP.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
k = 2 eggs, n = 6 floorsdrop(2,2)
x=1: max(drop(1,0)=0, drop(2,1)=1)=1; x=2: max(drop(1,1)=1, drop(2,0)=0)=1 → 1+1
drop(2,2) = 23C · Code with teaching comments
Reference implementation previewpublic int eggDrop(int k, int n) { return drop(k, n); } // drop(e, f): min worst-case drops with e eggs and f floorsExplore the full codeHide the full code
D · Why it works and complexityO(exponential) timeO(k + n) spaceOpen the invariant and proofExplore the proofHide the proof
The state is just two numbers — eggs left and floors in play — yet the naive recursion re-explores the same (e, f) endlessly. Two small state variables plus heavy overlap is the standard cue to memoize over a 2-D grid; the only twist versus ordinary DP is the min-of-max minimax body.
ComplexityO(exponential) time, O(k + n) space — Each call tries f drop floors, each forking into two subproblems, with no caching — the tree is exponential in n. Recursion depth is O(k + n).
E · Edge cases and pitfalls5n = 0 — drop(k, 0) = 0 — nothing to test.Explore edge casesHide edge cases
Edge cases handled
n = 0drop(k, 0) = 0 — nothing to test.k = 1drop(1, f) = f — single-egg linear scan.
Pitfalls
- Taking min instead of max over break/survive — that solves the lucky case, not the guaranteed worst case.
- Forgetting the one-egg base case and trying to binary search with a single egg.
- Skipping this approach — the minimax recurrence is exactly what the interviewer wants to hear first.
Approach 2 of 3
Classic 2-D DP — Memoization / Tabulation on (eggs, floors)
1Hint 1Explore hintHide hint
drop(e, f) returns the same value every call. Cache it in a 2-D table indexed by eggs and floors.
2Hint 2Explore hintHide hint
Bottom-up: dp[e][0] = 0, dp[e][1] = 1, dp[1][f] = f. Fill dp[e][f] by trying every drop floor x and taking 1 + min_x max(dp[e-1][x-1], dp[e][f-x]).
3Hint 3Explore hintHide hint
The inner scan over x is O(f). Because dp[e-1][x-1] increases and dp[e][f-x] decreases in x, the optimal x can be found by binary search, cutting the inner loop to O(log f).
A · Core idea
Cache the minimax recurrence so each (e, f) is solved once. Either memoize the recursion or fill a 2-D table bottom-up: dp[e][f] is the minimum worst-case drops with e eggs and f floors. Seed the base cases dp[e][0] = 0, dp[e][1] = 1, and dp[1][f] = f, then for every (e, f) try each drop floor x and keep 1 + min over x of max(dp[e-1][x-1], dp[e][f-x]).
The mental shift: the answer depends only on (eggs, floors). However you arrived at a state with e eggs and f floors left, the optimal continuation is a fixed number, so a 2-D cache collapses all duplicate work. There are k·n states, and scanning the drop floor costs O(n) per state — hence O(k·n²).
Why the inner scan can be binary-searched. As the drop floor x rises, dp[e-1][x-1] (the break branch) grows and dp[e][f-x] (the survive branch) shrinks. The worst case max(...) is minimized near their crossover, and because one term is monotonically increasing and the other monotonically decreasing, you can binary search for that crossover instead of scanning all x — turning the inner O(n) into O(log n) and the whole thing into O(k·n·log n).
Why these base cases. dp[e][1] = 1 (one floor, one drop), dp[e][0] = 0 (nothing to test), and dp[1][f] = f (one egg forces a linear climb). Every larger state is built on top of these.
A language note worth saying out loud. The top-down (memoized) version recurses up to O(k + n) deep. In Java that's fine; in Python the default recursion limit is about 1000, so for n near 10⁴ a memoized recursion will hit RecursionError. That's exactly why the bottom-up table (or the flipped DP below) is the safer choice in Python — it uses iteration, no call stack.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
k = 2 eggs, n = 10 floors (bottom-up dp[e][f])row e=1
dp[1][f] = f for all f (linear scan)
base row ready4C · Code with teaching comments
Reference implementation previewpublic int eggDrop(int k, int n) { int[][] dp = new int[k + 1][n + 1]; for (int e = 1; e <= k; e++) { dp[e][0] = 0; dp[e][1] = 1;Explore the full codeHide the full code
D · Why it works and complexityO(k·n²) timeO(k·n) spaceOpen the invariant and proofExplore the proofHide the proof
This is the standard DP upgrade — recurrence plus a cache keyed on the true state — applied to a minimax body. The non-obvious bonus is monotonicity: the break branch rises and the survive branch falls in x, so the inner minimization is unimodal and binary-searchable. Spotting that monotonic structure is what separates the O(k·n²) answer from the O(k·n·log n) one.
ComplexityO(k·n²) time, O(k·n) space — There are O(k·n) states (e, f). Resolving each scans up to O(n) drop floors → O(k·n²) time. Binary-searching the crossover point reduces the inner work to O(log n), giving O(k·n·log n). The table is O(k·n).
E · Edge cases and pitfalls6k = 1 — Only the dp[1][f] = f row is used → returns n.Explore edge casesHide edge cases
Edge cases handled
k = 1Only the dp[1][f] = f row is used → returns n.n = 1dp[k][1] = 1 for any k — one drop settles a single floor.k very largeEggs stop being the bottleneck; the answer matches ⌈log₂(n+1)⌉ (binary search).
Pitfalls
- Memoizing recursively in Python for n near 10⁴ — exceeds the ~1000 recursion limit; iterate bottom-up instead.
- Scanning all x when a binary search on the monotone crossover would cut it to O(log n).
- Forgetting dp[1][f] = f and accidentally letting one egg 'binary search'.
Approach 3 of 3 · Optimal
Flipped DP — Max Floors per Trial, dp[e][t] (Optimal)
1Hint 1Explore hintHide hint
Instead of 'min drops for n floors', ask the inverse: with e eggs and t trials, what's the MAXIMUM number of floors you can fully resolve?
2Hint 2Explore hintHide hint
With one drop (this trial) at the right floor: if it breaks, dp[e-1][t-1] floors below are coverable; if it survives, dp[e][t-1] floors above are coverable; plus the floor you just tested. So dp[e][t] = dp[e-1][t-1] + dp[e][t-1] + 1.
3Hint 3Explore hintHide hint
Increase t from 1 upward until dp[k][t] ≥ n; that smallest t is the answer. You can keep just a 1-D array over eggs, updated each trial (iterate eggs DESCENDING).
A · Core idea
Flip the optimization. Define dp[e][t] as the maximum number of floors you can fully resolve with e eggs and t allowed trials. The answer to the original problem is the smallest t such that dp[k][t] ≥ n.
The recurrence, read forward. Spend your first of t trials dropping an egg at a cleverly chosen floor. Two outcomes:
- It breaks: you have
e-1eggs andt-1trials left to resolve the floors below — that'sdp[e-1][t-1]floors. - It survives: you have
eeggs andt-1trials to resolve the floors above — that'sdp[e][t-1]floors.
Plus the one floor you just tested sits exactly between those two ranges. So a single trial lets you cover dp[e-1][t-1] + dp[e][t-1] + 1 floors total: dp[e][t] = dp[e-1][t-1] + dp[e][t-1] + 1.
Why this is dramatically faster. The classic DP scans every possible drop floor (O(n) per state). This version has no inner search at all — each dp[e][t] is a constant-time sum of two previously computed values. You just grow t until the coverage reaches n. Because coverage grows combinatorially (dp[e][t] = C(t,1) + C(t,2) + … + C(t,e)), t is usually around log n when eggs are plentiful, so the loop is short.
Why a 1-D array suffices. dp[e][t] depends only on dp[e][t-1] (same egg, previous trial) and dp[e-1][t-1] (one fewer egg, previous trial). Keeping a single array indexed by eggs and updating it each trial works if you iterate eggs descending — so dp[e-1] still holds its t-1 value when you read it (the same trick as 0/1 knapsack's descending sweep).
Why this is exact, not a heuristic. The flipped DP is provably equivalent to the minimax: the optimal classic strategy at each step balances the break and survive branches, which is precisely the additive structure this recurrence captures. It returns the identical answer, just computed from the other direction.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
k = 2 eggs, n = 10 floorsArray state
start (0 trials)
no floors covered yet
4C · Code with teaching comments
D · Why it works and complexityO(k·n) timeO(k) spaceOpen the invariant and proofExplore the proofHide the proof
Inverting the objective — from 'minimize trials for n floors' to 'maximize floors for t trials' — turns a quadratic minimax search into a constant-time recurrence. That 'flip the unknown' move is a recurring trick in hard DP: when minimizing one quantity is expensive, try maximizing the dual quantity and binary-search / increment over the answer. The same idea optimizes problems like 'minimum days/operations to reach a target'.
ComplexityO(k·n) time, O(k) space — Each additional trial updates k egg-entries in O(1) each. The number of trials needed is at most n (and typically O(log n) when eggs are plentiful), so the loop runs O(n) times worst case → O(k·n) time, O(k) space.
E · Edge cases and pitfalls6n = 0 — dp[k] = 0 ≥ 0 from the start; loop never runs → 0 trials.Explore edge casesHide edge cases
Edge cases handled
n = 0dp[k] = 0 ≥ 0 from the start; loop never runs → 0 trials.k = 1dp[1] grows by 1 each trial, so it takes n trials to reach n — matches the linear scan.k ≥ log₂(n+1)Coverage doubles roughly each trial, so trials ≈ ⌈log₂(n+1)⌉ — binary search emerges automatically.
Pitfalls
- Iterating eggs ASCENDING in the 1-D version — dp[e-1] would already be this trial's value, corrupting the recurrence.
- Returning dp[k] instead of the trial counter — dp[k] is floors covered, not the number of drops.
- Looping trials up to a fixed cap instead of 'until dp[k] ≥ n' — pick the stopping condition, not a guessed bound.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int eggDrop(int k, int n) { int[] dp = new int[k + 1]; // dp[e] = floors coverable with e eggs at the current trial count int trials = 0; while (dp[k] < n) { trials++;Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Min instead of max over outcomes
You must survive whichever outcome nature picks, so the cost of a drop floor is 1 + the WORSE of break/survive. Taking min assumes you get lucky and gives an unachievable, too-small answer.
Explore the code comparisonHide the code comparison
Min instead of max over outcomes
You must survive whichever outcome nature picks, so the cost of a drop floor is 1 + the WORSE of break/survive. Taking min assumes you get lucky and gives an unachievable, too-small answer.
Don't write this
worst = 1 + min(dp[e - 1][x - 1], dp[e][f - x]) # assumes the lucky branchWrite this instead
worst = 1 + max(dp[e - 1][x - 1], dp[e][f - x]) # must handle the worse branch2Ascending egg sweep in the flipped 1-D DP
dp[e][t] needs dp[e-1] at trial t-1. Iterating eggs ascending overwrites dp[e-1] with its trial-t value before dp[e] reads it, breaking the recurrence — the same hazard as 0/1 knapsack's loop direction.
Explore the code comparisonHide the code comparison
Ascending egg sweep in the flipped 1-D DP
dp[e][t] needs dp[e-1] at trial t-1. Iterating eggs ascending overwrites dp[e-1] with its trial-t value before dp[e] reads it, breaking the recurrence — the same hazard as 0/1 knapsack's loop direction.
Don't write this
for (int e = 1; e <= k; e++) { // ASCENDING — wrong
dp[e] = dp[e] + dp[e - 1] + 1;
}Write this instead
for (int e = k; e >= 1; e--) { // DESCENDING — keeps dp[e-1] at t-1
dp[e] = dp[e] + dp[e - 1] + 1;
}3Returning coverage instead of trials
In the flipped DP, dp[k] is the number of floors you can clear, not the number of drops. The answer is the trial counter at the moment dp[k] first reaches n.
Explore the code comparisonHide the code comparison
Returning coverage instead of trials
In the flipped DP, dp[k] is the number of floors you can clear, not the number of drops. The answer is the trial counter at the moment dp[k] first reaches n.
Don't write this
while dp[k] < n:
trials += 1
for e in range(k, 0, -1):
dp[e] = dp[e] + dp[e - 1] + 1
return dp[k] # returns floors covered, not dropsWrite this instead
while dp[k] < n:
trials += 1
for e in range(k, 0, -1):
dp[e] = dp[e] + dp[e - 1] + 1
return trials # the number of dropsRevise
Carry the pattern into the interview
Pattern to remember
Minimax DP — minimize the worst-case number of trials
Code pattern to memorize
Classic: dp[e][f] = 1 + min over x in 1..f of max(dp[e-1][x-1], dp[e][f-x])
Flipped (optimal): dp[e][t] = dp[e-1][t-1] + dp[e][t-1] + 1; answer = least t with dp[k][t] >= nRules to remember
- 1It's a minimax: you choose the drop floor to MINIMIZE the worst case, and the adversary (nature) picks the worse of the two outcomes (break vs survive). That nested
min over x of max(...)is the whole problem. - 2When the egg breaks at floor
x, you lose an egg and only floors below matter:dp[e-1][x-1]. When it survives, you keep the egg and only floors above matter:dp[e][f-x]. - 3Base cases:
dp[e][0] = 0(no floors → 0 drops),dp[e][1] = 1(one floor → one drop),dp[1][f] = f(one egg forces linear scan from the bottom). - 4The flipped DP asks the inverse question — 'how many floors can
ttrials clear?' — and is the fastest:dp[e][t] = dp[e-1][t-1] + dp[e][t-1] + 1, increasetuntil it coversn. - 5One egg means you cannot binary search — a break would leave you unable to continue, so you must climb floor by floor. That's why
dp[1][f] = f.
Use this pattern when
- Minimize the worst-case number of tests under a limited number of 'destructible' probes
- Each test has a binary outcome that either consumes a resource or doesn't, splitting the search space
- You must guarantee success against the worst placement, not the average case
- Threshold-finding where a failed probe can't be reused (eggs, pressure tests, rate limits)
Choose another pattern when
- Eggs are unlimited (or k ≥ log₂ n) → pure binary search, ⌈log₂(n+1)⌉ drops
- You optimize the AVERAGE number of drops, not the worst case → a different (probabilistic) DP
- Only one egg → trivially n drops, no DP needed
- You just need any working strategy, not the optimal one → linear scan suffices
Interview takeaway
Egg Drop is the canonical minimax DP: minimize over your choice, maximize over the adversary's outcome. The break/survive split (dp[e-1][x-1] vs dp[e][f-x]) is the model to remember. When the classic O(k·n²) is too slow, flip the question to 'max floors per t trials' for an O(k·n) — even O(k·log n) — solution. The same minimax shape appears in guessing-game and worst-case search problems.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternCanonical minimax DP — minimize your choice, maximize over the adversarial outcome. Recognize it when you must guarantee finding a threshold in the worst case with a limited budget of destructible probes. The break/survive split powers the classic dp[e][f]; flipping to dp[e][t] (floors per trial) is the fast O(k·n) form and the same trick appears in Guess Number Higher or Lower II.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Super Egg DropComing soonThe LeetCode form with large n — the flipped dp[e][t] DP is the intended O(k·n) (effectively O(k·log n)) solution.
- Guess Number Higher or Lower IIComing soonAnother minimax DP: minimize the worst-case cost of a guessing game over an interval.
- Burst BalloonsComing soonDifferent structure (interval DP) but the same 'optimize over a choice, fix the right pivot' mindset.
- Two Eggs, n Floors (closed form)Coming soonFor k = 2, the answer is the smallest t with t(t+1)/2 ≥ n — the triangular-number special case of the flipped DP.