887. Super Egg Drop
Problem Description
The problem presents a situation where you have k
identical eggs and a building with n
floors. The goal is to find the highest floor f
from which you can drop an egg without it breaking. The catch is that there is an unknown threshold floor where any egg dropped from a floor above it will break, and dropping from f
or lower will not break the egg. To figure out this threshold f
, you can perform a series of egg drops starting from any floor. If the egg breaks, you lose it permanently. If it doesn't, you can retrieve it and use it again.
Your task is to determine the minimum number of moves needed to find the threshold floor f
with absolute certainty, employing the best strategy possible given the number of eggs and floors.
Intuition
Discovering f
involves a trade-off between minimizing the number of moves and ensuring that the eggs are enough to definitively find the threshold. If you have only one egg, you have to start from the first floor and go up one floor at a time, which would result in the worst case of n
drops. With more eggs, you can attempt a more efficient binary search-like approach.
The solution is not immediately apparent, as we must strike a balance between the risk of breaking an egg and the information gained from each drop. The intuition behind the optimal strategy is to equalize the risk of moving up or down, which leads to a decision-making process at each step. The risk is defined in terms of how many additional drops we might need.
We want to choose a floor x
to drop from such that the number of drops needed if the egg breaks is as close as possible to the number of drops needed if it does not break. This minimizes the worst-case scenario after each drop, thereby minimizing the overall number of drops needed to discover f
.
Dynamic Programming (DP) is used here, where we remember past results and use them to construct solutions to new problems. The dfs
function calculates the minimum number of moves needed with i
floors and j
eggs. By caching these results, we avoid recomputing them, drastically increasing efficiency.
The solution uses binary search inside the dfs
function to find the critical point x
which equilibrates the worst-case drops below and above x
. Then we return the smaller of the two risks (plus one for the current drop) and cache this result to use in future calculations. We repeat the process until we have the number of moves needed for n
floors and k
eggs.
Learn more about Math, Binary Search and Dynamic Programming patterns.
Solution Approach
The implementation employs a top-down dynamic programming approach, where the solution to the problem is broken down into subproblems that are solved recursively. The data structure that supports this implementation is a hash table implicitly created through the use of the cache
decorator, which caches the results of the recursive calls thus avoiding duplicate computation.
Here's the walk-through of the implementation:
- We define a recursive function
dfs(i, j)
which represents the minimum number of moves required to find out the threshold floorf
withi
floors andj
eggs. - The recursive function has two base cases:
- If there are no floors (
i < 1
), no further moves are needed. - If we have only one egg (
j == 1
), our only option is to start from the first floor and go up one at a time which takesi
moves (worst case).
- If there are no floors (
- The recursive case uses binary search to find the most efficient floor to drop an egg. It initializes two pointers,
l
andr
, which represent the range within which to search for this optimal floor. - A while loop performs the binary search. The middle floor within the current range is computed as
mid = (l + r + 1) >> 1
. We consider two scenarios:- Dropping an egg from floor
mid
and it breaks. We now have a problem ofmid - 1
floors andj - 1
eggs. - Dropping an egg from floor
mid
and it doesn't break. We are left with ani - mid
floors problem and stillj
eggs.
- Dropping an egg from floor
- For each mid, we calculate the number of moves needed in both scenarios
(a)
and(b)
respectively. We aim to minimize the maximum risk, so we adjust the binary search range based on whether(a)
is less than or equal to(b)
or not. - Once the optimal floor to check is found (at the convergence of
l
andr
), the function returns the maximum of the two calculated moves plus one for the current move, since whether the egg breaks or not, we've used a move. - The
@cache
decorator ensures that the results for each pair ofi
andj
are saved and thus not recalculated multiple times. - Finally, we invoke the
dfs(n, k)
function to get the minimum number of moves required withn
floors andk
eggs.
The recursive function employs a depth-first search (hence the naming dfs
) traversing through various scenarios using the given eggs and floors. It cleverly balances the exploration via binary search, which is a significant optimization over a naive approach.
This algorithm is a blend of binary search, for efficiently narrowing down the floors to check, and dynamic programming, which ensures that intermediate solutions are stored for reuse to minimize the total number of calculations needed.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a small example where we have 2
identical eggs (k = 2)
and a 6
floor building (n = 6)
. We want to find the highest floor from which we can drop an egg without it breaking, using the least number of drops possible.
- We start by calling the recursive function
dfs(6, 2)
aiming to find the threshold floorf
in the most efficient way. - Since we have more than one egg, we can optimize our search and don't need to check each floor sequentially. We will use a binary search-like approach to decide the floor to test from. We set
l = 1
andr = 6
as our initial range. - During our first iteration in the binary search, we calculate the middle floor, which is
mid = (1 + 6 + 1) >> 1
, which simplifies tomid = 4
. - We now have two scenarios to consider:
- The egg breaks at
mid
(floor 4
), which meansf < 4
. We are then left with3
floors to check and1
less egg (dfs(3, 1)
). - The egg doesn't break at
mid
(floor 4
), indicatingf >= 4
. We now have2
floors left to check with the same2
eggs (dfs(2, 2)
).
- The egg breaks at
- Let's say we start by assuming the egg breaks at
floor 4
. The worst-case scenario will require us to check3
more floors sequentially(3 moves)
with our last remaining egg, as we placel = 1
andr = 3
. - On the other hand, if the egg doesn't break at
floor 4
, we testfloor 5
next (incrementl
to5
) because iffloor 4
is safe, we don't need to checkfloor 4
again. - If the egg breaks at
floor 5
, that meansf
isfloor 4
. If it doesn't, we only havefloor 6
left to test. Either way, we are making only1
additional move for this scenario. - We compare the number of moves in both the scenarios,
3
if it breaks and1
if it doesn't break. Since we want to minimize the worst-case number of moves, we adjust our binary search to checkfloor 3
next. - If the egg breaks at
floor 3
, we now need to check fromfloor 1
up, costing us2
moves (2
sequential floors with the last egg). If it doesn't break, we checkfloor 4
next, costing us a total of2
moves (the previously checkedfloor 3
plus testingfloor 4
next). - The middle ground between
2
and2
moves is consistent, so we continue this process, balancing the risk until we findf
. - Each result found on each step is cached by our
dfs
function thanks to the@cache
decorator, avoiding unnecessary recalculations. - Eventually,
dfs(6, 2)
returns3
as the minimum number of moves required to findf
with certainty.
By employing both dynamic programming and binary search, this highly optimized strategy efficiently reduces the number of moves needed to figure out the threshold floor f
for any given k
eggs and n
floors.
Solution Implementation
1from functools import lru_cache
2
3class Solution:
4 def superEggDrop(self, eggs: int, floors: int) -> int:
5 # Decorator to cache results of the recursive calls to reduce
6 # computation by not recalculating the same scenarios
7 @lru_cache(maxsize=None)
8 def drop_egg(moves: int, remaining_eggs: int) -> int:
9 # Base case: no moves needed if no floors
10 if moves == 0:
11 return 0
12 # Base case: if only one egg left, we need to check each floor
13 if remaining_eggs == 1:
14 return moves
15
16 # Initialize binary search bounds
17 low, high = 1, moves
18 # Perform binary search to find the minimum number of moves
19 while low < high:
20 mid = (low + high) // 2
21 # Recursively check dropping egg from the mid floor
22 # breaks: we have mid - 1 floors left, and one less egg
23 breaks = drop_egg(mid - 1, remaining_eggs - 1)
24 # no_break: we have moves - mid floors left with the same number of eggs
25 no_break = drop_egg(moves - mid, remaining_eggs)
26
27 # Narrow down the search space based on comparison
28 if breaks <= no_break:
29 low = mid
30 else:
31 high = mid - 1
32
33 # The result is the max of breaking and not breaking scenarios plus one for the current move
34 return max(drop_egg(low - 1, remaining_eggs - 1), drop_egg(moves - low, remaining_eggs)) + 1
35
36 # Call the recursive function starting with all floors and all eggs
37 return drop_egg(floors, eggs)
38
1class Solution {
2 // Memoization cache to hold the results of subproblems
3 private int[][] memo;
4
5 // Entry method for calculating the minimum number of moves
6 public int superEggDrop(int k, int n) {
7 memo = new int[n + 1][k + 1];
8 return findMinMoves(n, k);
9 }
10
11 // Helper method using Depth-First Search (DFS) to find the minimum moves
12 private int findMinMoves(int floors, int eggs) {
13 // The base case: if there are no floors, no moves are required
14 if (floors < 1) {
15 return 0;
16 }
17 // If there's only one egg, we need to check each floor starting from the first
18 if (eggs == 1) {
19 return floors;
20 }
21 // If we have already computed this state, return the stored result
22 if (memo[floors][eggs] != 0) {
23 return memo[floors][eggs];
24 }
25
26 // Binary search to find the critical floor in optimal manner
27 int low = 1, high = floors;
28 while (low < high) {
29 // Note: Using bitwise right-shift to divide by 2
30 int mid = (low + high + 1) >> 1;
31
32 // Recursively find outcomes for dropping an egg from the mid floor
33 // a: egg breaks (decrease egg count, lower half)
34 // b: egg doesn't break (same egg count, upper half)
35 int a = findMinMoves(mid - 1, eggs - 1);
36 int b = findMinMoves(floors - mid, eggs);
37
38 // Move our search space according to which scenario is worse
39 // as we want to prepare for the worst case
40 if (a <= b) {
41 low = mid;
42 } else {
43 high = mid - 1;
44 }
45 }
46
47 // Combine the worst case and add one for the current move
48 memo[floors][eggs] = Math.max(findMinMoves(low - 1, eggs - 1), findMinMoves(floors - low, eggs)) + 1;
49
50 // Return the minimum moves required
51 return memo[floors][eggs];
52 }
53}
54
1#include <vector>
2#include <functional>
3#include <cstring>
4using namespace std;
5
6class Solution {
7public:
8 // Function to find the minimum number of attempts needed in the worst case to find the critical floor.
9 int superEggDrop(int k, int n) {
10 // Initialize a memoization table where the rows represent the number of floors
11 // and the columns represent the number of eggs available.
12 vector<vector<int>> memo(n + 1, vector<int>(k + 1, 0));
13
14 // Define a recursive lambda function to perform depth-first search
15 // 'i' represents floors, and 'j' represents eggs.
16 function<int(int, int)> dfs = [&](int floors, int eggs) -> int {
17 // If there are no floors, no attempts are needed.
18 if (floors < 1) {
19 return 0;
20 }
21 // If there is only one egg, we need 'floors' attempts, as we need to start from the first floor.
22 if (eggs == 1) {
23 return floors;
24 }
25 // If we have already computed this state, return the result from the memo table.
26 if (memo[floors][eggs]) {
27 return memo[floors][eggs];
28 }
29 // Perform a binary search to find the critical floor in the optimal way
30 int low = 1, high = floors;
31 while (low < high) {
32 int mid = (low + high + 1) >> 1;
33 int breakCount = dfs(mid - 1, eggs - 1); // Egg breaks
34 int notBreakCount = dfs(floors - mid, eggs); // Egg doesn't break
35 // We want to balance the worst case of both scenarios (egg breaking and not breaking)
36 if (breakCount <= notBreakCount) {
37 low = mid;
38 } else {
39 high = mid - 1;
40 }
41 }
42 // After binary search, store the result in the memo table.
43 memo[floors][eggs] = max(dfs(low - 1, eggs - 1), dfs(floors - low, eggs)) + 1;
44 return memo[floors][eggs];
45 };
46
47 // Call our recursive function starting with 'n' floors and 'k' eggs.
48 return dfs(n, k);
49 }
50};
51
1// Function to calculate the minimum number of attempts needed to find the critical floor
2// from which an egg will break, given k eggs and n floors.
3function superEggDrop(k: number, n: number): number {
4 // Memoization table where `dp[n][k]` will represent the minimum number of attempts
5 // needed to find the critical floor with `n` floors and `k` eggs.
6 const dp: number[][] = new Array(n + 1).fill(0).map(() => new Array(k + 1).fill(0));
7
8 // Helper function using Depth-First Search approach to find the minimum number of attempts needed.
9 function dfs(floors: number, eggs: number): number {
10 // Base case: no floors require 0 attempts, and 1 floor requires 1 attempt.
11 if (floors < 1) {
12 return 0;
13 }
14 // If there's only one egg, we need a number of attempts equal to the number of floors.
15 if (eggs === 1) {
16 return floors;
17 }
18 // If result was already calculated, return the stored value from memoization table.
19 if (dp[floors][eggs]) {
20 return dp[floors][eggs];
21 }
22
23 let low = 1;
24 let high = floors;
25 // Use binary search to minimize the worst-case number of attempts.
26 while (low < high) {
27 const mid = Math.floor((low + high + 1) / 2);
28 const attemptsIfEggBreaks = dfs(mid - 1, eggs - 1); // Egg breaks, check lower half.
29 const attemptsIfEggDoesNotBreak = dfs(floors - mid, eggs); // Egg doesn't break, check upper half.
30
31 // We want to balance the number of attempts between the egg breaking and not breaking cases,
32 // to ensure the number of attempts is the minimum worst-case scenario.
33 if (attemptsIfEggBreaks <= attemptsIfEggDoesNotBreak) {
34 low = mid;
35 } else {
36 high = mid - 1;
37 }
38 }
39
40 // Store the result in the memoization table and return.
41 // Add one to include the current attempt.
42 dp[floors][eggs] = Math.max(dfs(low - 1, eggs - 1), dfs(floors - low, eggs)) + 1;
43 return dp[floors][eggs];
44 }
45
46 // Call the DFS helper function starting with the given number of floors and eggs.
47 return dfs(n, k);
48}
49
Time and Space Complexity
The provided code defines a superEggDrop
method that attempts to find the minimum number of attempts required to find the critical floor in a building with n
floors using k
eggs, where the critical floor is defined as the lowest floor from which an egg dropped will break.
The time complexity and space complexity analysis for this code is as follows:
Time complexity
The time complexity of the provided code is O(kn log n)
. This is because we have a memoized depth-first search (DFS) with dfs(n, k)
calls. For each state (i, j)
corresponding to i
floors and j
eggs, we perform a binary search to find the minimum attempts which run in O(log i)
. Since i
can go up to n
and we need to compute this for every egg from 1 to k
, the time complexity is the product of these values.
To express this in a formula, we have:
T(k, n)
being the time complexity fork
eggs andn
floors,T(k, n) = k * O(n log n)
since we run the binary search (O(log n)
) for each floor up ton
for each egg.
Thus, the time complexity is O(kn log n)
.
Space complexity
The space complexity of the code is O(kn)
due to the memoization that stores the results of every subproblem (i, j)
. There are n
possible floors and k
possible eggs, hence the space needed to store the results for all subproblems is proportional to the product of these two.
The formula for space complexity is:
S(k, n) = k * n
, whereS
denotes space complexity.
Therefore, the space complexity is O(kn)
.
Learn more about how to find time and space complexity quickly using problem constraints.
How many ways can you arrange the three letters A, B and C?
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.