Leetcode 887. Super Egg Drop

Problem Description

In this problem you are given K eggs and a building with N number of floors from 1 to N. You need to find the maximum floor (F) from where the egg can be dropped without breaking. We know that if an egg breaks from a floor F, it will also break from any floor higher than F. If the egg does not break from a floor F, it will also not break from any floor less than F. You want to find out the maximum floor (F) in the least possible number of egg drop moves, regardless of the initial value of F.

Solution Approach

To solve this problem, we can use dynamic programming. The idea is to minimize the worst possible number of moves needed to find F, over all possible first moves. If we drop from the i-th floor in our first move, we should consider the maximum of two situations:

1. The egg breaks and we're left with K-1 eggs and i-1 floors, dp[K-1][i-1].

2. The egg does not break and we are left with K eggs and N-i floors,dp[K][N-i].

Our approach will be to compute dp[K][N] for all 1 <= K <= 100 and 1 <= N <= 10000.

For example, consider K=2, and N=6.

If we drop the egg from the 1st floor and it does not break, we have 5 remaining floors and still 2 eggs.

If we drop the egg from the 3rd floor:

• If it breaks, we have 2 floors and 1 egg remaining.
• If it does not break, we have 3 floors and 2 eggs remaining.

In both of these cases, we ensure we only need to make a total of 3 moves in the worst case to find F.

Python Solution

1
2python
3class Solution:
4    def superEggDrop(self, k: int, n: int) -> int:
5        dp = [[0 for _ in range(n + 1)] for _ in range(k + 1)]
6        
7        for i in range(1, k + 1):
8            for j in range(1, n + 1):
9                dp[i][j] = 1 + dp[i - 1][j - 1] + dp[i][j - 1]
10                if dp[i][j] >= n:
11                    return j
12        return n

Java Solution

1
2java
3class Solution {
4    public int superEggDrop(int K, int N) {
5        int dp[][] = new int[N + 1][K + 1];
6        int m = 0;
7        while (dp[m][K] < N) {
8            m++;
9            for (int i = 1; i <= K; i++)
10                dp[m][i] = dp[m - 1][i - 1] + dp[m - 1][i] + 1;
11        }
12        return m;
13    }
14}

JavaScript Solution

1
2javascript
3var superEggDrop = function(k, n) {
4    let dp = Array(n + 1).fill(0);
5
6    for (let m = 1; m <= n; m++) {
7        for (let i = k; i > 0; i--) {
8            dp[i] += dp[i - 1] + 1;
9            if (dp[i] >= n) {
10                return m;
11            }
12        }
13    }
14    return n;
15};

C++ Solution

1
2cpp
3class Solution {
4public:
5    int superEggDrop(int K, int N) {
6        vector<int> dp(N + 1, 0);
7        for(int m = 1; m <= N; m++) {
8            for(int i = K; i > 0; i--){
9                dp[i] += dp[i - 1] + 1;
10                if(dp[i] >= N) return m;
11            }
12        }
13        return N;
14    }
15};

C# Solution

1
2csharp
3public class Solution {
4    public int SuperEggDrop(int K, int N) {
5        int[] dp= new int[K+1];
6        int m = 0;
7        for (m = 0; dp[K] < N; m++)
8            for (int i=K; i>0; i--)
9                dp[i] += dp[i-1] + 1;
10        return m;
11    }
12}

In all the above solutions, K is number of eggs and N is number of floors. We initialize a 1D or 2D dp array to zero. We sequentially iterate for every move till the number of maximum floors the eggs can be dropped from does not reach N. If this number >= N, we return the current move m. For every move m we update the values in the dp array up to number of egg drops, which is the total floors can be dropped from in the worst case plus 1. These solutions have O(KN) time complexity and O(N) or O(KN) space complexity depending on 1D or 2D dp array.## Optimization

We can further optimize the above solutions by observing that the egg drop problem exhibits optimal substructure and overlapping subproblems, which are the key components of dynamic programming.

Optimal Substructure: The optimal solution for the egg drop problem with K eggs and N floors can be achieved by obtaining the optimal solutions for K-1 eggs and fewer than N floors and K eggs and the remaining floors. We choose the maximum of these two results since we are interested in the worst-case scenario.

Overlapping Subproblems: Subproblems in the egg drop problem share the same subproblems. For example, in the above solutions, dp[i-1][j-1] and dp[i][j-1] overlap, where i is the number of eggs and j is the number of floors.

By utilizing these two properties, we can implement a solution to the egg drop problem using Binary Search, which reduces the time complexity to O(K log N).

Python Solution with Binary Search

1
2python
3class Solution:
4    def superEggDrop(self, K: int, N: int) -> int:
5        def f(x):
6            ans = 0
7            r = 1
8            for i in range(1, K+1):
9                r *= x-i+1
10                r //= i
11                ans += r
12                if ans >= N: break
13            return ans
14
15        lo, hi = 1, N
16        while lo < hi:
17            mi = (lo + hi) // 2
18            if f(mi) < N:
19                lo = mi + 1
20            else:
21                hi = mi
22        return lo

Java Solution with Binary Search

1
2java
3class Solution {
4    public int superEggDrop(int K, int N) {
5        int lo = 1, hi = N;
6        while (lo < hi) {
7            int mi = (lo + hi) / 2;
8            if (f(mi, K) < N)
9                lo = mi + 1;
10            else
11                hi = mi;
12        }
13        return lo;
14    }
15    public int f(int x, int K) {
16        int ans = 0, r = 1;
17        for (int i = 1; i <= K; ++i) {
18            r *= x - i + 1;
19            r /= i;
20            ans += r;
21            if (ans >= Integer.MAX_VALUE) break;
22        }
23        return ans;
24    }
25}

In these solutions, f(x) calculates the maximum number of floors that can be checked with x moves and K eggs. We then use binary search to find the smallest x such that f(x) >= N.