How to Solve Super Egg Drop Problem with Dynamic Programming
Find the minimum number of egg drops needed to know the lowest floor in a building from which an egg won’t break.
Problem Description
There are E eggs (= allowed egg breaks), a building with F floors [1 ≥ F] and a special floor S [0 ≤ S ≤ F] - any unbroken egg dropped at a floor higher than S will break and any egg dropped at or below this floor will not break.
Given that an unbroken egg can be dropped from any floor, what is the minimum number of egg drops D [1 ≤ D ≤ F] needed in order to find S in the worst case?
Input1: E =1 , F=1 | Output1: D=1
Input2: E =1 , F=2 | Output2: D=2
Input3: E =1 , F=7 | Output3: D=7
Input4: E =2 , F=7 | Output4: D=4
Input5: E =3 , F=7 | Output5: D=3
Common confusion points:
- What is “Worst case”? It means that egg breaking must happen only when the search range from top to bottom is exhausted.
- What is “floor0” in the range for special floor? Treat it as a basement where egg drop isn’t allowed but can be used for reference. Example: S=0 incase the the egg breaks on floor 1 which would mean any drop above floor 0 will result in a break.
🍳 Solutions
Linear Search
Take an egg to floor1 and start dropping it by going up 1 floor at a time until it breaks or we go beyond the top floor. The worst case is going through all floors [O(F)] to find S=F.
Unfortunately, this algorithm will not work because we have to find the minimum number of egg drops needed to find S which will be smaller than S in several cases.
Modified Binary Search
A typical binary search will get us O(Log2(F)) egg drops. Here we will repeatedly do an egg drop from the middle floor in a range (bottom to top floor) to check whether it breaks. In the illustration below, you can see bottom=1, top=7 and middle=4 for a building in the first iteration.
If the egg breaks at floor4, then this floor is above S because an egg will break on all floors above S. So bottom stays as 1 but top changes to middle-1=4 -1=3. If the egg doesn’t break at floor4, then this floor is below S because an egg will not break on any floor below S. So top stays as 7 but bottom changes to middle+1=4 +1=5. After the range change, we continually repeat this process until we find S. The worst case is going through Log2(F) floors to find that S=F or S=0.
This works great in a world with unlimited eggs (=egg breaks) but will be much less efficient with an egg break limit. In the scenario above, what if the first egg breaks from floor4 and then the second egg also breaks from floor2? Since there will be no additional eggs left to continue the algorithm, it will be impossible to find whether S=1 or S=0. To make this work, instead of dropping the second egg at floor2 we can take the second egg to the bottom(floor1) and do a linear search by dropping it as we go up 1 floor at a time.
Even with this modification, imagine a case with 1000 floors and 2 eggs, we will end up going through 500 floors anyways which is F/2 ~ O(F) in this case. Can we do better?
O(ExF) Complexity
Two Egg Breaks
Lets revisit the problem of F floors with a limit of 2 eggs for now along with the modified binary search algorithm we learnt to understand the basic theme of the algorithm.
Assume that we already know that X egg drops need to be performed to find S. Given these constraints, the first egg has to be dropped at floor X (jump to X directly). This is necessary to keep the egg drop count equal to X at the end.
When the first egg breaks, we start the linear search with the second egg from floor1.
X = 1 (drop at floor X with first egg)
+ X-1 (drops from floor 1 to floor X-1 with second egg)When the first egg doesn’t break at floor X, we can jump up by X-1 and drop it on the floor (X+(X-1))=2X-1. Incase the first egg breaks on this second drop, then we start the linear search at X+1, otherwise we continue to jump up.
X = 1 (drop at floor X with first egg)
+ 1 (drop at floor 2X-1 with first egg)
+ X-2 (drops from floor X+1 to floor 2X-2 with second egg)We keep reducing the jumps by one each time we jump up, until we only have one floor left. To generalize for 2 eggs, in worst case the sum of the jumps should be greater than or equal to the number of floors as follows:
X + (X-1) + (X-2) + … + 2 + 1 >= FLimited E Egg Breaks
Let’s recall a few things before we dive into the actual algorithm:
- Total number of floors in a building =
current floor
+ floors explored when egg breaks at current(bottom to current-1)
+ floors explored when egg doesn’t break at current(current+1 to top) - It is possible find egg drops from number of floors and vice-versa (as per the equation) under a constraint of egg breaks.
We have a 2-D matrix floors which is D x E and floors[d][e] is the number of floors that we can find S for with egg drops d and egg breaks e (basically the number of eggs) allowed.
floors[d][e] = 1 (new floor against new egg drop)
+ floors[d-1][e-1]
(floors with 1 less egg drop and 1 less egg break)
+ floors[d-1][e]
(floors with 1 less egg drop)floors[d][e] is the number of floors we can find S for with d egg drops and e egg breaks. As we drop a new egg, if egg breaks then S is below the current floor else it’s above the current floor. The total number of floors is the sum of the three values:
- current + floors below towards the bottom: 1 + floors[d-1][e-1] is total number of floors that we can get to from the bottom, given that the egg breaks on the new drop.
- floors above towards the top: floors[d-1][e] is the number of floors that we can get to from the new floor to the top.
Code
# Language: Java
# Time Complexity: O(ExF) because of the nested loop.public int superEggDrop(int E, int F) {
int[][] floors = new int[F+1][E+1];
for (int d=1; d<=F; d++) {
for (int e=1; e<=E; e++) {
floors[d][e] = 1
+ floors[d-1][e-1]
+ floors[d-1][e];
if (floors[d][e] >= F) {
return d;
}
}
}
return -1;
}
Lets discuss an example in detail; floors is 10 for for D=4 and E=2. The visualization of the floors matrix (for more dimensions than what the code will calculate) is as follows:
Notice how E=1 column values are for the linear search on the floors as only 1 egg break is allowed and E=2 column values follow the logic described in Two Egg Breaks section.
The algorithm steps are:
Step1: Drop egg at floor=floors(3,1)+1=3+1=4. We have 3 egg drops left. If broken, linear search from floor1 to floor3, else go to Step2.
Step2: Drop egg at floor=4+(4–1)=4+3=7. We have 2 egg drops left. If broken, linear search from floor5 to floor6, else go to Step3.
Step3: Drop egg at floor=7+(4–2)=9. We have 1 egg drop left. If broken, drop egg at floor 8 else at floor 9.
Special Thanks …
[1] Simplest - Python DP Solution with Detailed Explanation
[2] Classic DP Super Egg
[3] The Two Egg Problem
[4] 887. Super Egg Drop
Other Data Structure and Algorithms Articles you may like:
