Super Egg Drop solution and explanation
Google
9 more videos on this problem
花花酱 LeetCode 887. Super Egg Drop - 刷题找工作 EP 348Hua Hua · 23:50 · 4K views
LeetCode 887. Super Egg DropHappy Coding · 46:20 · 4K views
LeetCode 887. Super Egg Drop (Hard) | Dynamic Programming | C++Ascorbichelix · 9:27 · 4K views
LeetCode 887. Super Egg Drop | O(n * k) Worst case | O(k * log(n)) Avg ComplexityPrateek Mishra · 28:10 · 2K views
Super Egg Drop Part 1: O(KN^2) Time SolutionForAllEpsilon · 14:19 · 2K views
887. Super Egg Drop 鸡蛋掉落【LeetCode 力扣题解】LeetCode 力扣 · 5:00 · 785 views
Super Egg Drop - LeetCode 887 | Java | RECode Sep 2024 | NISHANTH SCoding Club PSGCT · 11:49 · 707 views
Leetcode887 Super Egg Drop及其变体！Dan Wang (Lily) · 33:03 · 588 views
887. Super Egg Drop | Leetcode | Egg Dropping problem | Dynamic ProgrammingADITYA PRAKASH · 23:18 · 470 views
Super Egg Drop | Leetcode #887 | dynamic programmingTechWills · 10:48 · 418 views
The problem
You are given k identical eggs and you have access to a building with n floors labeled from 1 to n.
You know that there exists a floor f where 0 <= f <= n such that any egg dropped at a floor higher than f will break, and any egg dropped at or below floor f will not break.
Each move, you may take an unbroken egg and drop it from any floor x (where 1 <= x <= n). If the egg breaks, you can no longer use it. However, if the egg does not break, you may reuse it in future moves.
Return the minimum number of moves that you need to determine with certainty what the value of f is.
Example 1:
Input: k = 1, n = 2 Output: 2 Explanation: Drop the egg from floor 1. If it breaks, we know that f = 0. Otherwise, drop the egg from floor 2. If it breaks, we know that f = 1. If it does not break, then we know f = 2. Hence, we need at minimum 2 moves to determine with certainty what the value of f is.
Example 2:
Input: k = 2, n = 6 Output: 3
Example 3:
Input: k = 3, n = 14 Output: 4
Constraints:
1 <= k <= 1001 <= n <= 104
Approach overview
Problem Overview: You are given K eggs and a building with N floors. An egg breaks if dropped from a floor higher than a certain threshold. The goal is to determine the minimum number of moves required to find that threshold floor in the worst case.
Approach 1: Dynamic Programming with Binary Search (Time: O(K * N * log N), Space: O(K * N))
This approach models the problem with a DP state dp[k][n], representing the minimum moves needed with k eggs and n floors. For each floor x you drop an egg from, two outcomes occur: the egg breaks (search below with k-1 eggs) or it survives (search above with k eggs). The worst-case cost becomes 1 + max(dp[k-1][x-1], dp[k][n-x]). Instead of checking every floor linearly, apply binary search because one side increases while the other decreases as x grows. This optimization significantly reduces transitions while keeping the DP formulation intuitive. Use this approach when you want a clear state definition and standard dynamic programming reasoning.
Approach 2: Mathematical DP on Moves (Time: O(K * log N), Space: O(K))
A more efficient formulation focuses on the number of moves instead of floors. Let dp[m][k] represent the maximum number of floors that can be tested with m moves and k eggs. The recurrence becomes dp[m][k] = dp[m-1][k-1] + dp[m-1][k] + 1. The first term represents the case where the egg breaks, the second where it survives, and the +1 accounts for the current floor. Increase the move count until dp[m][K] >= N. This works because each move expands the searchable range combinatorially. The logic relies on mathematical observation rather than floor-by-floor simulation, making it both elegant and fast. Concepts here intersect with combinatorics and mathematical reasoning.
Recommended for interviews: The mathematical DP approach is typically expected in strong interviews because it reduces the complexity to roughly O(K log N) and shows deeper insight into the problem structure. Still, starting with the DP state definition and explaining the binary-search optimization demonstrates solid dynamic programming fundamentals before presenting the optimal idea.
Approach 1: Dynamic Programming with Binary Search
In this approach, we use dynamic programming (DP) to solve the problem efficiently. The idea is to set up a DP table where dp[k][n] represents the minimum number of moves required to find the critical floor with k eggs and n floors.
We can use binary search to determine which floor to drop the egg from in each step, which helps to optimize the number of trials needed. The recurrence relation can be formulated as:
dp[k][n] = 1 + min(max(dp[k-1][x-1], dp[k][n-x])) for all 1 <= x <= n.
This relation means that for each floor x, you either continue with the remaining floors if the egg doesn't break, or with one fewer egg if it does break. The goal is to find the minimal worst-case scenario.
class Solution:
def superEggDrop(self, k: int, n: int) -> int:
dp = [[0] * (n + 1) for _ in range(k + 1)]
for i in range(1, k + 1):
dp[i][0] = 0
dp[i][1] = 1
for j in range(1, n + 1):
dp[1][j] = j
for i in range(2, k + 1):
for j in range(2, n + 1):
low, high = 1, j
while low <= high:
mid = (low + high) // 2
broken = dp[i - 1][mid - 1]
not_broken = dp[i][j - mid]
if broken > not_broken:
high = mid - 1
else:
low = mid + 1
dp[i][j] = min(dp[i][j], 1 + max(broken, not_broken))
return dp[k][n]
if __name__ == '__main__':
sol = Solution()
print(sol.superEggDrop(3, 14)) # Output: 4class Solution {
public int superEggDrop(int k, int n) {
int[][] dp = new int[k + 1][n + 1];
for (int i = 0; i <= k; i++) {
dp[i][0] = 0;
if (i > 0) dp[i][1] = 1;
}
for (int j = 0; j <= n; j++) {
dp[1][j] = j;
}
for (int i = 2; i <= k; i++) {
for (int j = 2; j <= n; j++) {
int low = 1, high = j, mid;
while (low <= high) {
mid = (low + high) / 2;
int broken = dp[i - 1][mid - 1];
int not_broken = dp[i][j - mid];
int cost = 1 + Math.max(broken, not_broken);
dp[i][j] = Math.min(dp[i][j], cost);
if (broken > not_broken) {
high = mid - 1;
} else {
low = mid + 1;
}
}
}
}
return dp[k][n];
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.superEggDrop(2, 6)); // Output: 3
}
}#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int superEggDrop(int k, int n) {
vector<vector<int>> dp(k + 1, vector<int>(n + 1, INT_MAX));
for (int i = 0; i <= k; ++i) {
dp[i][0] = 0;
if (i > 0) dp[i][1] = 1;
}
for (int j = 0; j <= n; ++j) {
dp[1][j] = j;
}
for (int i = 2; i <= k; ++i) {
for (int j = 2; j <= n; ++j) {
int low = 1, high = j, mid;
while (low <= high) {
mid = (low + high) / 2;
int broken = dp[i - 1][mid - 1];
int not_broken = dp[i][j - mid];
int cost = 1 + max(broken, not_broken);
dp[i][j] = min(dp[i][j], cost);
if (broken > not_broken) {
high = mid - 1;
} else {
low = mid + 1;
}
}
}
}
return dp[k][n];
}
int main() {
cout << superEggDrop(3, 14) << endl; // Output: 4
return 0;
}var superEggDrop = function(k, n) {
let dp = Array.from({ length: k + 1 }, () => Array(n + 1).fill(Infinity));
for (let i = 0; i <= k; i++) {
dp[i][0] = 0;
if (i > 0) dp[i][1] = 1;
}
for (let j = 0; j <= n; j++) {
dp[1][j] = j;
}
for (let i = 2; i <= k; i++) {
for (let j = 2; j <= n; j++) {
let low = 1, high = j;
while (low <= high) {
let mid = Math.floor((low + high) / 2);
let broken = dp[i - 1][mid - 1];
let notBroken = dp[i][j - mid];
dp[i][j] = Math.min(dp[i][j], 1 + Math.max(broken, notBroken));
if (broken > notBroken) {
high = mid - 1;
} else {
low = mid + 1;
}
}
}
}
return dp[k][n];
};
console.log(superEggDrop(2, 6)); // Output: 3#include <stdio.h>
#include <limits.h>
int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }
int superEggDrop(int k, int n) {
int dp[k + 1][n + 1];
for (int i = 0; i <= k; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0 || j == 0) {
dp[i][j] = 0;
} else if (i == 1) {
dp[i][j] = j;
} else {
dp[i][j] = INT_MAX;
int low = 1, high = j, mid;
while (low <= high) {
mid = (low + high) / 2;
int broken = dp[i - 1][mid - 1];
int not_broken = dp[i][j - mid];
int cost = 1 + max(broken, not_broken);
dp[i][j] = min(dp[i][j], cost);
if (broken > not_broken) {
high = mid - 1;
} else {
low = mid + 1;
}
}
}
}
}
return dp[k][n];
}
int main() {
printf("%d\n", superEggDrop(2, 6)); // Output: 3
return 0;
}using System;
public class Solution {
public int SuperEggDrop(int k, int n) {
int[,] dp = new int[k + 1, n + 1];
for (int i = 0; i <= k; i++) {
dp[i, 0] = 0;
if (i > 0) {
dp[i, 1] = 1;
}
}
for (int j = 0; j <= n; j++) {
dp[1, j] = j;
}
for (int i = 2; i <= k; i++) {
for (int j = 2; j <= n; j++) {
int low = 1, high = j, mid, ans = int.MaxValue;
while (low <= high) {
mid = low + (high - low) / 2;
int broken = dp[i - 1, mid - 1];
int notBroken = dp[i, j - mid];
ans = Math.Min(ans, 1 + Math.Max(broken, notBroken));
if (broken > notBroken) {
high = mid - 1;
} else {
low = mid + 1;
}
}
dp[i, j] = ans;
}
}
return dp[k, n];
}
public static void Main(string[] args) {
Solution sol = new Solution();
Console.WriteLine(sol.SuperEggDrop(3, 14)); // Output: 4
}
}In Python, the 2D list dp is used to represent the DP table. The method starts by initializing base cases and iteratively computes the minimum trials needed using a binary search approach for every possible egg-floor combination. This prevents the naive way of checking each floor sequentially. The test block calls the superEggDrop method with 3 eggs and 14 floors.
Time Complexity: O(k * n * log n) primarily due to the binary search.
Space Complexity: O(k * n) to store the DP matrix.
Approach 2: Mathematical Approach with DP
Here, we use a mathematical approach combined with dynamic programming. Instead of trying to calculate the minimum number of moves directly, we use a theoretical approach that considers the problem of breaking down moves into binary forms.
We change the problem into one of maximizing the number of floors we can test with a given number of drops. We can calculate m moves where the result is T[k][m] = T[k-1][m-1] + T[k][m-1] + 1. If T[k][m] ≥ n, we found the minimum m.
class Solution:
def superEggDrop(self, k: int, n: int) -> int:
dp = list(range(n + 1))
for i in range(2, k + 1):
dp2 = [0] * (n + 1)
x = 1
for j in range(1, n + 1):
while x < j and max(dp[x - 1], dp2[j - x]) > max(dp[x], dp2[j - x - 1]):
x += 1
dp2[j] = 1 + max(dp[x - 1], dp2[j - x])
dp = dp2
return dp[n]
if __name__ == '__main__':
sol = Solution()
print(sol.superEggDrop(3, 14)) # Output: 4class Solution {
public int superEggDrop(int k, int n) {
int[] dp = new int[n + 1];
for (int i = 0; i <= n; i++) dp[i] = i;
for (int i = 2; i <= k; i++) {
int[] dpNew = new int[n + 1];
int x = 1;
for (int j = 1; j <= n; j++) {
while (x < j && Math.max(dp[x - 1], dpNew[j - x]) > Math.max(dp[x], dpNew[j - x - 1])) {
x++;
}
dpNew[j] = 1 + Math.max(dp[x - 1], dpNew[j - x]);
}
dp = dpNew;
}
return dp[n];
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.superEggDrop(2, 6)); // Output: 3
}
}#include <iostream>
#include <vector>
using namespace std;
int superEggDrop(int k, int n) {
vector<int> dp(n + 1, 0);
for (int i = 0; i <= n; ++i) dp[i] = i;
for (int i = 2; i <= k; ++i) {
vector<int> dp_new(n + 1, 0);
int x = 1;
for (int j = 1; j <= n; ++j) {
while (x < j && max(dp[x - 1], dp_new[j - x]) > max(dp[x], dp_new[j - x - 1])) {
++x;
}
dp_new[j] = 1 + max(dp[x - 1], dp_new[j - x]);
}
dp = dp_new;
}
return dp[n];
}
int main() {
cout << superEggDrop(2, 6) << endl; // Output: 3
return 0;
}var superEggDrop = function(k, n) {
let dp = [...Array(n + 1).keys()];
for (let i = 2; i <= k; i++) {
const dpNew = new Array(n + 1).fill(0);
let x = 1;
for (let j = 1; j <= n; j++) {
while (x < j && Math.max(dp[x - 1], dpNew[j - x]) > Math.max(dp[x], dpNew[j - x - 1])) {
x++;
}
dpNew[j] = 1 + Math.max(dp[x - 1], dpNew[j - x]);
}
dp = dpNew;
}
return dp[n];
};
console.log(superEggDrop(3, 14)); // Output: 4#include <stdio.h>
#include <limits.h>
int superEggDrop(int k, int n) {
int dp[n + 1];
for (int i = 0; i <= n; i++) {
dp[i] = i;
}
for (int i = 2; i <= k; i++) {
int dp_new[n + 1];
for (int j = 0; j <= n; j++) {
dp_new[j] = j;
}
int x = 1;
for (int j = 1; j <= n; j++) {
while (x < j && max(dp[x - 1], dp_new[j - x]) > max(dp[x], dp_new[j - x - 1])) {
x++;
}
dp_new[j] = 1 + max(dp[x - 1], dp_new[j - x]);
}
for (int j = 1; j <= n; j++) {
dp[j] = dp_new[j];
}
}
return dp[n];
}
int main() {
printf("%d\n", superEggDrop(2, 6)); // Output: 3
return 0;
}using System;
public class Solution {
public int SuperEggDrop(int k, int n) {
int[] dp = new int[n + 1];
for (int i = 0; i <= n; i++) dp[i] = i;
for (int i = 2; i <= k; i++) {
int[] dpNew = new int[n + 1];
int x = 1;
for (int j = 1; j <= n; j++) {
while (x < j && Math.Max(dp[x - 1], dpNew[j - x]) > Math.Max(dp[x], dpNew[j - x - 1])) {
x++;
}
dpNew[j] = 1 + Math.Max(dp[x - 1], dpNew[j - x]);
}
dp = dpNew;
}
return dp[n];
}
public static void Main(string[] args) {
Solution sol = new Solution();
Console.WriteLine(sol.SuperEggDrop(2, 6)); // Output: 3
}
}This Python function effectively trades-off possibilities within minimal steps, placing rather than examining it maximally in each isolated instance with swapping between list trend indexes.
While it maintains 1D layer exchange through in-loop iterations for any egg number up to maximal n.
Time Complexity: O(k * n).
Space Complexity: O(n).
Approach 3: Default Approach
function superEggDrop(k: number, n: number): number {
const f: number[][] = new Array(n + 1).fill(0).map(() => new Array(k + 1).fill(0));
const dfs = (i: number, j: number): number => {
if (i < 1) {
return 0;
}
if (j === 1) {
return i;
}
if (f[i][j]) {
return f[i][j];
}
let l = 1;
let r = i;
while (l < r) {
const mid = (l + r + 1) >> 1;
const a = dfs(mid - 1, j - 1);
const b = dfs(i - mid, j);
if (a <= b) {
l = mid;
} else {
r = mid - 1;
}
}
return (f[i][j] = Math.max(dfs(l - 1, j - 1), dfs(i - l, j)) + 1);
};
return dfs(n, k);
}func superEggDrop(k int, n int) int {
f := make([][]int, n+1)
for i := range f {
f[i] = make([]int, k+1)
}
var dfs func(i, j int) int
dfs = func(i, j int) int {
if i < 1 {
return 0
}
if j == 1 {
return i
}
if f[i][j] != 0 {
return f[i][j]
}
l, r := 1, i
for l < r {
mid := (l + r + 1) >> 1
a, b := dfs(mid-1, j-1), dfs(i-mid, j)
if a <= b {
l = mid
} else {
r = mid - 1
}
}
f[i][j] = max(dfs(l-1, j-1), dfs(i-l, j)) + 1
return f[i][j]
}
return dfs(n, k)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming with Binary Search | Time Complexity: |
| Mathematical Approach with DP | Time Complexity: |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with Binary Search | O(K * N * log N) | O(K * N) | When explaining classic DP state transitions and optimizing the drop-floor search with binary search |
| Mathematical DP on Moves | O(K * log N) | O(K) | Best for optimal performance and interviews where mathematical insight into the problem is expected |
Frequently asked questions
Is Super Egg Drop easy or hard?
Super Egg Drop is classified as a hard problem because it requires recognizing a non-obvious DP formulation and optimizing it. The straightforward DP approach is already complex, and the optimal mathematical DP requires deeper insight into how moves expand the searchable floor range.
Super Egg Drop Python/Java solution
Both Python and Java implementations typically use dynamic programming. The DP with binary search approach builds a table dp[k][n], while the optimized method iteratively updates dp[m][k] based on previous moves. Python often uses lists for compact DP updates, while Java commonly uses arrays.
How to solve Super Egg Drop in O(n)?
A near-linear strategy comes from the mathematical DP formulation using moves instead of floors. Each iteration increases the number of moves and updates dp[m][k] = dp[m-1][k-1] + dp[m-1][k]. The algorithm stops once the reachable floors exceed N, giving a runtime close to O(K log N) in practice.
What is the best approach for Super Egg Drop?
The most efficient approach uses a mathematical dynamic programming formulation based on the number of moves. Instead of tracking floors directly, dp[m][k] stores how many floors can be tested with m moves and k eggs. This reduces the complexity to roughly O(K log N) and avoids checking every floor explicitly.
Is Super Egg Drop asked at Google/Amazon/Meta?
Super Egg Drop is considered a classic hard dynamic programming problem and has appeared in interviews at major tech companies including Google, Amazon, and Meta. Interviewers use it to evaluate DP reasoning, optimization skills, and the ability to discover mathematical patterns in state transitions.
What data structure is used in Super Egg Drop?
The main data structure is a dynamic programming table or array. In the binary search solution, a 2D DP table stores states for eggs and floors. In the mathematical optimization, a 1D or 2D DP array tracks how many floors can be tested with a given number of moves and eggs.
What is the time complexity of Super Egg Drop?
The classic DP solution with binary search runs in O(K * N * log N) time and O(K * N) space. The optimized mathematical DP approach improves this to about O(K * log N) time with O(K) space by computing how many floors can be tested with a given number of moves.