Skip to main content
Talentd

Super Egg Drop - Solution & Explanation

HardMathBinary SearchDynamic Programming19 min readAsked at: Amazon, Microsoft, Google +2
Practice this problem

Problem Statement

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 <= 100
  • 1 <= 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.

This C implementation creates a 2D array dp where each entry dp[i][j] represents the minimum number of moves required with i eggs for j floors.

The algorithm initializes the base cases: if there's only one egg, the number of moves is j (since we need to try every floor sequentially), and for zero floors or zero eggs, no move is required.

For each scenario, the function iteratively searches the best floor to drop using binary search, updating the DP table with the minimum number of attempts needed using the recurrence relation explained above.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(k * n * log n) because each fill operation of the DP table involves a binary search over the number of floors.
Space Complexity: O(k * n) because of the DP table holding computed results.

Try this approach in the editor β†’

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.

In this C solution, we use a similar 1D DP concept with two arrays that take shifts for operations. It reduces the grains of move possibilities (instead of examining choice permutations and trays them shallow iterations). For each egg beyond the first, the new entries find a balance between fewer and extra floors, inheriting an O(n) step management budget.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(k * n), because we directly shift through combinations.
Space Complexity: O(n) since we're using array-based exploratory floor encoding.

Try this approach in the editor β†’

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor β†’

Complexity Comparison

ApproachComplexity
Dynamic Programming with Binary Search

Time Complexity: O(k * n * log n) because each fill operation of the DP table involves a binary search over the number of floors.
Space Complexity: O(k * n) because of the DP table holding computed results.

Mathematical Approach with DP

Time Complexity: O(k * n), because we directly shift through combinations.
Space Complexity: O(n) since we're using array-based exploratory floor encoding.

Default Approachβ€”

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dynamic Programming with Binary SearchO(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 MovesO(K * log N)O(K)Best for optimal performance and interviews where mathematical insight into the problem is expected

Video Solution

θŠ±θŠ±ι…± LeetCode 887. Super Egg Drop - εˆ·ι’˜ζ‰Ύε·₯作 EP 348 β€’ Hua Hua β€’ 4,795 views views

Watch 9 more video solutions β†’

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.

Ready to solve this problem?

Practice Super Egg Drop with our built-in code editor and test cases.

Practice on FleetCode
Previous

Egg Drop With 2 Eggs and N Floors