Problem

You are given k identical eggs and you have access to a building with n floors labeled from 1 to n.

You know that there exists a floor f where 0 <= f <= n such that any egg dropped at a floor higher than f will break, and any egg dropped at or below floor f will not break.

Each move, you may take an unbroken egg and drop it from any floor x (where 1 <= x <= n). If the egg breaks, you can no longer use it. However, if the egg does not break, you may reuse it in future moves.

Return the minimum number of moves that you need to determine with certainty what the value of f is.

Examples

Example 1:

1
2
3
4
5
6
7

Input: k = 1, n = 2
Output: 2
Explanation: 
Drop the egg from floor 1. If it breaks, we know that f = 0.
Otherwise, drop the egg from floor 2. If it breaks, we know that f = 1.
If it does not break, then we know f = 2.
Hence, we need at minimum 2 moves to determine with certainty what the value of f is.

Example 2:

1
2

Input: k = 2, n = 6
Output: 3

Example 3:

1
2

Input: k = 3, n = 14
Output: 4

Solution

Method 1 - Using DP

  1. Problem Breakdown:
    • You have k eggs and n floors.
    • If an egg breaks, the floors above are unsafe (the critical floor is in the floors below).
    • If an egg doesn’t break, the critical floor is in the floors above.
  2. Goal:
    • Minimise the worst-case number of moves required to find the floor f.
  3. Key Observations:
    • If you have just one egg, you’ll need to check each floor sequentially from 1 to n. This takes n moves in the worst case.
    • If you have many eggs, you can use a binary-like search pattern to minimise the number of moves—splitting the problem space into halves repeatedly.
  4. Approach:
    • We’ll define dp[k][n] as the minimum number of moves required to find f with k eggs and n floors.
    • When dropping an egg from floor x:
      • If the egg breaks, the problem reduces to dp[k-1][x-1] (fewer eggs and fewer floors below x).
      • If the egg doesn’t break, the problem reduces to dp[k][n-x] (same eggs but fewer floors above x).
    • The recurrence relation becomes: 
      1

      dp[k][n] = 1 + min(max(dp[k-1][x-1], dp[k][n-x]) for x in range(1, n+1)).
  5. Optimisation:
    • Instead of testing every floor x linearly, a binary search can be applied on x due to the “minimum of maximums” structure.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution {

    public int superEggDrop(int k, int n) {
        // Initialize DP table
        int[][] dp = new int[k + 1][n + 1];

        // Fill the table
        for (int e = 1; e <= k; e++) { // e for eggs
            for (int f = 1; f <= n; f++) { // f for floors
                if (e == 1) {
                    dp[e][f] = f; // If 1 egg, we test all floors
                } else if (f == 1) {
                    dp[e][f] = 1; // If 1 floor, only 1 move is required
                } else {
                    // Binary search optimisation
                    int lo = 1, hi = f;
                    while (lo < hi) {
                        int mid = (lo + hi) / 2;
                        if (dp[e - 1][mid - 1] < dp[e][f - mid]) {
                            lo = mid + 1;
                        } else {
                            hi = mid;
                        }
                    }
                    dp[e][f] = 1 + dp[e - 1][lo - 1];
                }
            }
        }

        return dp[k][n];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution:
    def superEggDrop(self, k: int, n: int) -> int:
        # Define dp table
        dp: list[list[int]] = [[0] * (n + 1) for _ in range(k + 1)]
        
        # Fill the table
        for e in range(1, k + 1):  # e for eggs
            for f in range(1, n + 1):  # f for floors
                if e == 1:
                    dp[e][f] = f  # If 1 egg, we need to test all floors
                elif f == 1:
                    dp[e][f] = 1  # If 1 floor, only 1 move is required
                else:
                    # Binary search optimisation
                    lo, hi = 1, f
                    while lo < hi:
                        mid = (lo + hi) // 2
                        if dp[e-1][mid-1] < dp[e][f-mid]:
                            lo = mid + 1
                        else:
                            hi = mid
                    dp[e][f] = 1 + dp[e-1][lo-1]
        
        return dp[k][n]

Complexity

  • ⏰ Time complexity: O(k * n * log(n))
    • The brute-force DP approach has O(k * n^2) complexity due to nested loops.
    • Using binary search for the inner loop reduces the complexity to O(k * n * log(n)).
  • 🧺 Space complexity: O(k*n). The space complexity is O(k * n) because of the DP table.