What is the Egg Drop Problem?
Understand the egg drop dynamic programming problem, its minimax recurrence, and how to answer this hard interview question.
Expected Interview Answer
The egg drop problem asks for the minimum number of trial drops needed, in the worst case, to find the exact floor in an n-floor building at which eggs start breaking, given k eggs, and it is solved with dynamic programming where eggs[k][n] depends on the worst outcome of dropping from every candidate floor.
For a chosen drop floor x, either the egg breaks, leaving k-1 eggs and x-1 floors below still to search, or it survives, leaving k eggs and n-x floors above still to search; the worst case for that choice is 1 plus the maximum of those two subresults. The optimal number of trials for k eggs and n floors is the minimum over all choices of x of that worst case, which naively costs O(k*n^2) since each of the O(k*n) states tries O(n) floor choices. Because the break-outcome cost increases and the survive-outcome cost decreases monotonically as x increases, binary search over x reduces this to O(k*n log n), and a fully different formulation — asking how many floors can be covered with m trials and k eggs — solves the whole problem in O(k*n) time. It is a classic example of reformulating a minimax DP into an easier-to-compute equivalent question.
- Classic minimax dynamic programming: minimize the worst-case number of trials
- Naive O(k*n^2), improvable to O(k*n log n) with binary search on the drop floor
- Alternate O(k*n) formulation inverts the question to floors-coverable-by-trials
- Demonstrates how reformulating a DP question can drastically cut complexity
AI Mentor Explanation
A groundskeeper must find the exact height at which a stadium roof panel starts cracking under repeated ball impacts, using a limited number of test panels and wanting the fewest test throws in the worst case. Throwing from a given height either cracks the panel, meaning fewer panels remain but only the lower heights still need checking, or it survives, meaning all panels remain but only the higher heights still need checking. The worst-case throws needed from that height is one plus whichever of those two remaining problems is harder, and the groundskeeper picks the throw height that minimizes this worst case across all choices. This mirrors the egg drop problem exactly: minimizing the guaranteed-worst-case number of trials given a limited number of test items and a range to search.
Step-by-Step Explanation
Step 1
Define the state
eggs[k][n] = minimum worst-case trials needed with k eggs and n floors to check.
Step 2
Branch on a chosen floor x
If it breaks: eggs[k-1][x-1] remains. If it survives: eggs[k][n-x] remains. Worst case is 1 + max of the two.
Step 3
Minimize over all floor choices
eggs[k][n] = min over x in 1..n of (1 + max(eggs[k-1][x-1], eggs[k][n-x])).
Step 4
Optimize the search over x
Since break-cost rises and survive-cost falls monotonically with x, binary search x for O(k*n log n), or invert to an O(k*n) floors-covered-by-trials formulation.
What Interviewer Expects
- Correctly state the recurrence with the break/survive branch and the +1 for the current trial
- Explain why it is a worst-case (minimax) optimization, not an average-case one
- Give the naive O(k*n^2) complexity and know at least one optimization exists
- Handle the base cases: 1 egg needs n trials linear search, 0 floors needs 0 trials
Common Mistakes
- Forgetting the +1 for the current trial in the recurrence
- Averaging break and survive outcomes instead of taking the worst case (max)
- Not recognizing binary search over x is valid due to monotonicity
- Confusing this with a simple binary search problem when k=1 forces linear search
Best Answer (HR Friendly)
“The egg drop problem is about finding the exact floor where eggs start breaking in a building, using as few drops as possible in the worst case, when you only have a limited number of eggs to spare. I solve it with dynamic programming by considering, for every possible drop floor, what happens if the egg breaks versus survives, and picking the floor that minimizes the worst outcome.”
Code Example
def egg_drop(eggs, floors):
# dp[k][n] = min worst-case trials with k eggs, n floors
dp = [[0] * (floors + 1) for _ in range(eggs + 1)]
for n in range(1, floors + 1):
dp[1][n] = n # one egg forces linear search
for k in range(2, eggs + 1):
for n in range(1, floors + 1):
best = float("inf")
for x in range(1, n + 1):
breaks = dp[k - 1][x - 1]
survives = dp[k][n - x]
worst = 1 + max(breaks, survives)
best = min(best, worst)
dp[k][n] = best
return dp[eggs][floors]Follow-up Questions
- How would you reduce the time complexity using binary search on the drop floor?
- How does the alternate “floors coverable with m trials” formulation solve this in O(k*n)?
- What is the answer when you have only 1 egg, or unlimited eggs?
- How would you adapt this if drops could also cost different amounts depending on floor?
MCQ Practice
1. In the egg drop recurrence, what happens to the number of eggs when a dropped egg breaks?
A broken egg is used up, so the remaining subproblem has k-1 eggs and only the floors below still to search.
2. What is the naive time complexity of the egg drop DP with k eggs and n floors?
Each of the O(k*n) states tries up to n candidate floors, giving O(k*n^2) total.
3. With exactly 1 egg and n floors, what is the minimum worst-case number of trials?
With only one egg you cannot risk binary search since a break ends testing, so you must go floor by floor, needing n trials worst case.
Flash Cards
What does the egg drop problem minimize? — The worst-case number of trial drops needed to find the critical floor, given a limited number of eggs.
What is the core recurrence branch? — Dropping from floor x either breaks (k-1 eggs, x-1 floors below) or survives (k eggs, n-x floors above); worst case is 1 + max of the two.
What is the naive time complexity? — O(k*n^2), improvable to O(k*n log n) via binary search on the drop floor.
What is the answer for 1 egg and n floors? — n trials, since you must test floors one at a time from the bottom.