Super Egg Drop

Hard Dynamic Programming 2D DP Original on LeetCode

Reported atGoldman Sachs

Super Egg Drop is a hard dynamic programming problem solved with the 2d dp pattern. The best approach, optimal (moves-and-eggs dp), runs in O(k · m), with m <= n time and O(k) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (dp over every first floor) up.

Problem

You have k identical eggs and a building with floors numbered 1 to n. Somewhere there is a threshold floor f with 0 <= f <= n: an egg dropped from any floor above f breaks, and an egg dropped from floor f or below survives and can be used again. A broken egg is gone for good.

Each move, you pick an unbroken egg and drop it from any floor you like. Return the minimum number of moves that guarantees you learn the exact value of f, no matter where the threshold actually is.

Examples

Example 1

Input
k = 1, n = 3
Output
3
Why
With one egg you cannot risk skipping a floor: drop from floor 1, then 2, then 3. In the worst case all three drops are needed.

Example 2

Input
k = 2, n = 10
Output
4
Why
Drop the first egg from floors 4, 7, 9, 10 in turn; when it breaks, scan the floors just below with the second egg. Every case finishes in at most 4 drops, and 3 drops can cover at most 6 floors with 2 eggs.

Example 3

Input
k = 3, n = 25
Output
5
Why
With 3 eggs, 4 moves can separate at most 14 floors and 5 moves up to 25, so 5 is the minimum.

Constraints

  • 1 <= k <= 100
  • 1 <= n <= 10^4

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 15 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (DP over every first floor)O(k · n²)O(k · n)
Better (DP with binary search on the drop floor)O(k · n · log n)O(k · n)
Optimal (moves-and-eggs DP)O(k · m), with m <= nO(k)

1Brute force (DP over every first floor)

TimeO(k · n²)k · n states, each trying up to n floors.
SpaceO(k · n)The full dp table.

Let dp[e][f] be the minimum drops needed with e eggs and f uncertain floors. Dropping at floor x costs 1 + max(dp[e-1][x-1], dp[e][f-x]). Try every x.

  1. dp[e][0] = 0 and dp[1][f] = f.
  2. For e from 2 to k and f from 1 to n: dp[e][f] = min over x in 1..f of 1 + max(dp[e-1][x-1], dp[e][f-x]).
  3. Return dp[k][n].
class Solution {
    public int superEggDrop(int k, int n) {
        int[][] dp = new int[k + 1][n + 1];
        for (int f = 1; f <= n; f++) dp[1][f] = f;
        for (int e = 2; e <= k; e++) {
            for (int f = 1; f <= n; f++) {
                int best = Integer.MAX_VALUE;
                for (int x = 1; x <= f; x++) {
                    int worst = 1 + Math.max(dp[e - 1][x - 1], dp[e][f - x]);
                    best = Math.min(best, worst);
                }
                dp[e][f] = best;
            }
        }
        return dp[k][n];
    }
}

2Better (DP with binary search on the drop floor)

TimeO(k · n · log n)k · n states, each with a binary search over up to n floors.
SpaceO(k · n)The full dp table.

In 1 + max(dp[e-1][x-1], dp[e][f-x]) the first term never decreases as x grows and the second never increases. The minimum of their maximum sits where they cross, so binary search x instead of scanning it.

  1. Same table and base cases as before.
  2. For each (e, f), binary search x in [1, f]: if dp[e-1][x-1] < dp[e][f-x] move right (lo = x + 1), else move left (hi = x).
  3. Evaluate the cost at the crossing point and the point just before it, and keep the smaller.
class Solution {
    public int superEggDrop(int k, int n) {
        int[][] dp = new int[k + 1][n + 1];
        for (int f = 1; f <= n; f++) dp[1][f] = f;
        for (int e = 2; e <= k; e++) {
            for (int f = 1; f <= n; f++) {
                int lo = 1, hi = f;
                while (lo < hi) {
                    int x = (lo + hi) / 2;
                    if (dp[e - 1][x - 1] < dp[e][f - x]) lo = x + 1;
                    else hi = x;
                }
                int best = 1 + Math.max(dp[e - 1][lo - 1], dp[e][f - lo]);
                if (lo > 1) {
                    best = Math.min(best, 1 + Math.max(dp[e - 1][lo - 2], dp[e][f - lo + 1]));
                }
                dp[e][f] = best;
            }
        }
        return dp[k][n];
    }
}

3Optimal (moves-and-eggs DP)

TimeO(k · m), with m <= nEach move updates k entries, and the number of moves needed is at most n (and about log n when k is large).
SpaceO(k)One array of k + 1 counts.

Ask the reverse question: with m moves and e eggs, what is the largest number of floors cover[m][e] you can fully resolve? The first drop resolves its own floor; if the egg breaks you have m - 1 moves and e - 1 eggs for the floors below, otherwise m - 1 moves and e eggs for the floors above. So cover[m][e] = cover[m-1][e-1] + cover[m-1][e] + 1. Increase m until cover[m][k] >= n.

  1. Keep a 1D array cover[0..k], all zeros (zero moves resolve zero floors).
  2. Repeat: m++; for e from k down to 1, cover[e] = cover[e] + cover[e - 1] + 1 (going down reuses last round's values).
  3. Stop as soon as cover[k] >= n and return m.
class Solution {
    public int superEggDrop(int k, int n) {
        int[] cover = new int[k + 1];
        int m = 0;
        while (cover[k] < n) {
            m++;
            for (int e = k; e >= 1; e--) {
                cover[e] = cover[e] + cover[e - 1] + 1;
            }
        }
        return m;
    }
}

Edge cases to test

  • k = 1: the only safe strategy is a linear scan, so the answer is n
  • n = 1: a single drop decides it
  • Many eggs (k >= log2(n + 1)): the answer becomes the binary-search depth

Hints

Hint 1

Define the state as (eggs left, floors still uncertain). Dropping from floor x either breaks the egg (go below with one fewer egg) or not (go above with the same eggs). You must plan for the worse branch.

Hint 2

Trying every x costs O(n) per state. The 'breaks' branch grows with x and the 'survives' branch shrinks, so the best x can be found by binary search.

Hint 3

Flip the question: with m moves and e eggs, how many floors can you fully resolve? One drop splits into f(m-1, e-1) floors below, f(m-1, e) above, plus the floor itself.

FAQ

What is the best time complexity for Super Egg Drop?

Optimal (moves-and-eggs DP) runs in O(k · m), with m <= n time and O(k) extra space. Each move updates k entries, and the number of moves needed is at most n (and about log n when k is large).

Which pattern does Super Egg Drop use?

It is a dynamic programming problem that uses the 2d dp pattern. Other problems with the same pattern: Minimum Path Sum, Unique Paths, Unique Paths II.

Is there a brute force solution for Super Egg Drop?

Yes. Brute force (DP over every first floor) takes O(k · n²) time and O(k · n) space. Let dp[e][f] be the minimum drops needed with e eggs and f uncertain floors.

Which edge cases should I test for Super Egg Drop?

k = 1: the only safe strategy is a linear scan, so the answer is n; n = 1: a single drop decides it; Many eggs (k = log2(n + 1)): the answer becomes the binary-search depth.