Hard Problemsminimizationinterval

Egg Dropping Problem

Given k identical eggs and a building with n floors, where an egg dropped from at or above some unknown critical floor breaks and one dropped below it survives, find the minimum number of trial drops needed, in the worst case, to pin down that critical floor exactly.

Do this lesson first: coin change

Example input

3 eggs, 6 floors

Expected output

3

Break it down

Answer each question out loud before you open it. Getting it wrong here is the useful part. A revealed answer you never guessed at teaches you nothing.

dp[e][f] is the fewest drops that are GUARANTEED to find the critical floor among f floors when you hold e eggs, however the floors turn out. Two numbers name the state, eggs and floors, so the table is a rectangle, not a triangle. Watch the index convention, because the two counts start in different places: e counts eggs from 1 and f counts floors from 0. So dp[e][f] lives in grid row e - 1, the row labelled with e eggs, and in column f. dp[2][5] is the row labelled 2 eggs, column 5. Every dp[...] on this page, in the narration, the gates and the recurrence, uses that dp[eggs][floors] form, and so does the code below, which allocates a 0-egg row it never uses so that its indices match. The answer, all the eggs on all the floors, is the bottom-right cell. The cell holds a number of drops, not the plan that achieves it.

dp[e][f] = min over k from 1 to f of 1 + max(dp[e - 1][k - 1], dp[e][f - k]); dp[e][0] = 0, dp[1][f] = f

Ask where the FIRST drop happens: floor k, for some k from 1 to f. Two things can happen, and you do not get to choose which. If the egg breaks, the critical floor is k or below, you have e - 1 eggs left, and only the k - 1 floors below k still need checking: dp[e - 1][k - 1] more drops. If it survives, the critical floor is above k, you still have all e eggs, and the f - k floors above k are left: dp[e][f - k]. Only how many floors are left matters, not which ones, so floors k + 1 to f are the same problem as floors 1 to f - k. A guarantee has to hold in whichever case happens, so a first drop from floor k costs 1 + the LARGER of the two: a max, because the building picks the outcome. Then you pick k, so take the smallest such cost over every k: a min, because the floor is your choice. The min over choices is the move coin change makes, derived in its lesson at /courses/dynamic-programming/coin-change; what is new is that each choice is scored by its worse outcome before the min sees it. It is also the same loop over split points the convolution1d pages run, nth-catalan-number among them: there every split is summed, and here the floor k splits the building into below and above and only the cheapest split is kept.

dp[e][0] = 0 down column 0: with no floors there is nothing to find. dp[1][f] = f across the 1-egg row: with a single egg you cannot risk a break that leaves a floor untested, so you drop from floor 1, then 2, and on up, and in the worst case every one of the f floors gets a drop. Every other cell reads 2f cells: the row above at columns 0 to f - 1, one per floor k for the break, and its own row at columns f - 1 down to 0, one per floor k for the survival. All of them sit in the row above or to the left in the same row, so a row-major sweep, left to right along each row, has every read final before the cell needs it. As k rises the break side, dp[e - 1][k - 1], can only grow and the survive side, dp[e][f - k], can only shrink, which is why the best k sits where the two cross.

Tabulation over e(f + 1) cells, each scanning up to f first-drop floors, so O(e f²) time and O(e f) space; a cell reads only its own row and the row above, so two rows of f + 1 are enough. At 3 eggs and 6 floors that is 21 cells: 9 bases and 12 computes, which read 84 values between them. Top-down memoization from the answer saves exactly one cell at every slider size: nothing reads the last column, so the 2-egg cell there, dp[2][f], is never needed, and the recursion fills 2f - 1 of the 2f computed cells. The coverage count in the variations is far faster.

Time O(e × f²) for e eggs and f floorsSpace O(e × f), reducible to O(f) with two rows

Fill the table

The table pauses before each cell you have to supply. Type the value the recurrence gives, and the write animation confirms it.

Step not started

Press start. The animation stops at every cell YOUR recurrence must fill.

dp[e][0] = 0 down column 0: with no floors there is nothing to find. dp[1][f] = f across the 1-egg row: with a single egg you cannot risk a break that leaves a floor untested, so you drop from floor 1, then 2, and on up, and in the worst case every one of the f floors gets a drop. Every other cell reads 2f cells: the row above at columns 0 to f - 1, one per floor k for the break, and its own row at columns f - 1 down to 0, one per floor k for the survival. All of them sit in the row above or to the left in the same row, so a row-major sweep, left to right along each row, has every read final before the cell needs it. As k rises the break side, dp[e - 1][k - 1], can only grow and the survive side, dp[e][f - k], can only shrink, which is why the best k sits where the two cross.

Rows ↓
Cols →

0

1

2

3

4

5

6

1 egg

0

1

2

3

4

5

6

2 eggs

0

1

2

3

3 eggs

0

1

2

3

Rows ↓row e - 1: how many eggs you hold, so the row labelled 2 eggs is dp[2][...]

Cols →column f: how many floors are left to search, so the cell dp[e][f] is the fewest drops that always find the critical floor

egg-dropping.ts

1function eggDrop(eggs, floors) {
2 const dp = Array.from({ length: eggs + 1 }, () => new Array(floors + 1).fill(0));
3 for (let f = 1; f <= floors; f++) dp[1][f] = f;
4 for (let e = 2; e <= eggs; e++) {
5 for (let f = 1; f <= floors; f++) {
6 let best = Infinity;
7 for (let k = 1; k <= f; k++) {
8 const worse = Math.max(dp[e - 1][k - 1], dp[e][f - k]);
9 best = Math.min(best, 1 + worse);
10 }
11 dp[e][f] = best;
12 }
13 }
14 return dp[eggs][floors];
15}

Base caseComputedBeing readAnswer

The code, the trap, the variations

egg-dropping.ts

1function eggDrop(eggs, floors) {
2 const dp = Array.from({ length: eggs + 1 }, () => new Array(floors + 1).fill(0));
3 for (let f = 1; f <= floors; f++) dp[1][f] = f;
4 for (let e = 2; e <= eggs; e++) {
5 for (let f = 1; f <= floors; f++) {
6 let best = Infinity;
7 for (let k = 1; k <= f; k++) {
8 const worse = Math.max(dp[e - 1][k - 1], dp[e][f - k]);
9 best = Math.min(best, 1 + worse);
10 }
11 dp[e][f] = best;
12 }
13 }
14 return dp[eggs][floors];
15}

Where people go wrong

Scoring a drop by its BETTER outcome: 1 + min(dp[e - 1][k - 1], dp[e][f - k]) where the max belongs. It reads naturally, min everywhere for a minimisation problem, and it is badly wrong: a first drop from floor 1 always has a break side of dp[e - 1][0] = 0, so every computed cell comes out 1 and the answer reads 1 at every slider size, as if one drop could settle any building. The worst case is the whole point of the question, so the inner operation has to be the max. The other classic slip is reaching for binary search: drop from the lower middle floor, floor f / 2 rounded up, while you have more than one egg, then go floor by floor. On the 2-egg row it is right up to 8 floors and then wrong at 9, 10 and 11, needing 5, 5 and 6 drops where the table finds 4, 4 and 5, because halving spends an egg too early and leaves one egg facing a long climb. Round to the upper middle floor instead and the 2-egg row already goes wrong at 6 floors, 4 drops against 3. On the 3-egg row, the one the answer comes from, it happens to match at every slider size, which is exactly how it survives a few hand tests.

Flip the question: with t drops and e eggs, how many floors can you settle?
The state becomes (drops, eggs), and the min and the max both disappear: one drop either breaks, leaving t - 1 drops and e - 1 eggs for the floors below, or survives, leaving t - 1 drops and e eggs for the floors above, so c[t][e] = c[t - 1][e - 1] + c[t - 1][e] + 1. The answer is the smallest t with c[t][e] at least f. With 3 eggs that coverage runs 1, 3, 7, 14 for t = 1 to 4, so 6 floors need 3 drops and 11 floors need 4, the same answers as the table, in O(e × answer) time instead of O(e f²).
Find the best first-drop floor without trying every one.
The recurrence does not change; the scan over k does. The break side dp[e - 1][k - 1] never falls as k rises and the survive side dp[e][f - k] never rises, so the larger of the two can only fall and then only climb, and the best k is where the two sides cross. Binary search for that crossing takes O(log f) per cell instead of O(f), so the table costs O(e f log f).
Fix the eggs at 2.
Only the first two rows remain, and the 2-egg row has a closed form: with t drops, two eggs settle t(t + 1) / 2 floors (drop from floor t, then t + (t - 1), and so on, one floor less each time), so the answer is the smallest t with t(t + 1) / 2 at least f. On this page the 2-egg row reads 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5 from 1 to 11 floors, which is exactly that t. The classic 100 floors need 14.
Return the drop plan, not just the count.
The table is unchanged; remember the winning k at every cell. The plan is a tree, not a list: drop from the winning floor of dp[e][f], then follow dp[e - 1][k - 1] if the egg broke or dp[e][f - k] if it survived, shifting that cell's floors up by k. At 3 eggs and 6 floors the first drop is floor 3, and floor 4 ties with it.

Largest X Bordered Square Palindrome Partitioning