Super Egg Drop
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 <= 1001 <= 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.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
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.
| Approach | Time | Space |
|---|---|---|
| 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 <= n | O(k) |
1Brute force (DP over every first floor)
O(k · n²)k · n states, each trying up to n floors.O(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.
- dp[e][0] = 0 and dp[1][f] = f.
- 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]).
- 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];
}
}class Solution:
def superEggDrop(self, k: int, n: int) -> int:
dp = [[0] * (n + 1) for _ in range(k + 1)]
for f in range(1, n + 1):
dp[1][f] = f
for e in range(2, k + 1):
for f in range(1, n + 1):
best = float("inf")
for x in range(1, f + 1):
worst = 1 + max(dp[e - 1][x - 1], dp[e][f - x])
best = min(best, worst)
dp[e][f] = best
return dp[k][n]class Solution {
public:
int superEggDrop(int k, int n) {
vector<vector<int>> dp(k + 1, vector<int>(n + 1, 0));
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 = INT_MAX;
for (int x = 1; x <= f; x++) {
int worst = 1 + max(dp[e - 1][x - 1], dp[e][f - x]);
best = min(best, worst);
}
dp[e][f] = best;
}
}
return dp[k][n];
}
};function superEggDrop(k, n) {
const dp = Array.from({ length: k + 1 }, () => new Array(n + 1).fill(0));
for (let f = 1; f <= n; f++) dp[1][f] = f;
for (let e = 2; e <= k; e++) {
for (let f = 1; f <= n; f++) {
let best = Infinity;
for (let x = 1; x <= f; x++) {
const 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)
O(k · n · log n)k · n states, each with a binary search over up to n floors.O(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.
- Same table and base cases as before.
- 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).
- 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];
}
}class Solution:
def superEggDrop(self, k: int, n: int) -> int:
dp = [[0] * (n + 1) for _ in range(k + 1)]
for f in range(1, n + 1):
dp[1][f] = f
for e in range(2, k + 1):
below = dp[e - 1]
row = dp[e]
for f in range(1, n + 1):
lo, hi = 1, f
while lo < hi:
x = (lo + hi) // 2
if below[x - 1] < row[f - x]:
lo = x + 1
else:
hi = x
best = 1 + max(below[lo - 1], row[f - lo])
if lo > 1:
best = min(best, 1 + max(below[lo - 2], row[f - lo + 1]))
row[f] = best
return dp[k][n]class Solution {
public:
int superEggDrop(int k, int n) {
vector<vector<int>> dp(k + 1, vector<int>(n + 1, 0));
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 + max(dp[e - 1][lo - 1], dp[e][f - lo]);
if (lo > 1) {
best = min(best, 1 + max(dp[e - 1][lo - 2], dp[e][f - lo + 1]));
}
dp[e][f] = best;
}
}
return dp[k][n];
}
};function superEggDrop(k, n) {
const dp = Array.from({ length: k + 1 }, () => new Array(n + 1).fill(0));
for (let f = 1; f <= n; f++) dp[1][f] = f;
for (let e = 2; e <= k; e++) {
for (let f = 1; f <= n; f++) {
let lo = 1, hi = f;
while (lo < hi) {
const x = (lo + hi) >> 1;
if (dp[e - 1][x - 1] < dp[e][f - x]) lo = x + 1;
else hi = x;
}
let 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)
O(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).O(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.
- Keep a 1D array cover[0..k], all zeros (zero moves resolve zero floors).
- Repeat: m++; for e from k down to 1, cover[e] = cover[e] + cover[e - 1] + 1 (going down reuses last round's values).
- 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;
}
}class Solution:
def superEggDrop(self, k: int, n: int) -> int:
cover = [0] * (k + 1)
m = 0
while cover[k] < n:
m += 1
for e in range(k, 0, -1):
cover[e] = cover[e] + cover[e - 1] + 1
return mclass Solution {
public:
int superEggDrop(int k, int n) {
vector<long long> cover(k + 1, 0);
int m = 0;
while (cover[k] < n) {
m++;
for (int e = k; e >= 1; e--) {
cover[e] = min(cover[e] + cover[e - 1] + 1, (long long)INT_MAX);
}
}
return m;
}
};function superEggDrop(k, n) {
const cover = new Array(k + 1).fill(0);
let m = 0;
while (cover[k] < n) {
m++;
for (let 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.