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.
Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?
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 floorfwithifloors andjeggs. - 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 takesimoves (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,
landr, 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
midand it breaks. We now have a problem ofmid - 1floors andj - 1eggs. - Dropping an egg from floor
midand it doesn't break. We are left with ani - midfloors problem and stilljeggs.
- 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
landr), 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
@cachedecorator ensures that the results for each pair ofiandjare saved and thus not recalculated multiple times. - Finally, we invoke the
dfs(n, k)function to get the minimum number of moves required withnfloors andkeggs.
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.
Depth first search can be used to find whether two components in a graph are connected.
Example 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 floorfin 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 = 1andr = 6as 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 with3floors to check and1less egg (dfs(3, 1)). - The egg doesn't break at
mid(floor 4), indicatingf >= 4. We now have2floors left to check with the same2eggs (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 check3more floors sequentially(3 moves)with our last remaining egg, as we placel = 1andr = 3. - On the other hand, if the egg doesn't break at
floor 4, we testfloor 5next (incrementlto5) because iffloor 4is safe, we don't need to checkfloor 4again. - If the egg breaks at
floor 5, that meansfisfloor 4. If it doesn't, we only havefloor 6left to test. Either way, we are making only1additional move for this scenario. - We compare the number of moves in both the scenarios,
3if it breaks and1if it doesn't break. Since we want to minimize the worst-case number of moves, we adjust our binary search to checkfloor 3next. - If the egg breaks at
floor 3, we now need to check fromfloor 1up, costing us2moves (2sequential floors with the last egg). If it doesn't break, we checkfloor 4next, costing us a total of2moves (the previously checkedfloor 3plus testingfloor 4next). - The middle ground between
2and2moves is consistent, so we continue this process, balancing the risk until we findf. - Each result found on each step is cached by our
dfsfunction thanks to the@cachedecorator, avoiding unnecessary recalculations. - Eventually,
dfs(6, 2)returns3as the minimum number of moves required to findfwith 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)
381class 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}
541#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};
511// 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}
49What's the output of running the following function using the following tree as input?
1def serialize(root):
2 res = []
3 def dfs(root):
4 if not root:
5 res.append('x')
6 return
7 res.append(root.val)
8 dfs(root.left)
9 dfs(root.right)
10 dfs(root)
11 return ' '.join(res)
121import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4 StringJoiner res = new StringJoiner(" ");
5 serializeDFS(root, res);
6 return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10 if (root == null) {
11 result.add("x");
12 return;
13 }
14 result.add(Integer.toString(root.val));
15 serializeDFS(root.left, result);
16 serializeDFS(root.right, result);
17}
181function serialize(root) {
2 let res = [];
3 serialize_dfs(root, res);
4 return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8 if (!root) {
9 res.push("x");
10 return;
11 }
12 res.push(root.val);
13 serialize_dfs(root.left, res);
14 serialize_dfs(root.right, res);
15}
16Time 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 forkeggs andnfloors,T(k, n) = k * O(n log n)since we run the binary search (O(log n)) for each floor up tonfor 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, whereSdenotes space complexity.
Therefore, the space complexity is O(kn).
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?
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 Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.