# Super Egg Drop
**Difficulty:** HARD
[External](https://leetcode.com/problems/super-egg-drop)
Canonical: https://scaleengineer.com/dsa/problems/super-egg-drop
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
---
## 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.

**Example 1:**

**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:**

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

**Example 3:**

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

**Constraints:**

* `1 <= k <= 100`
* `1 <= n <= 104`

# Approaches
## Dynamic Programming (Quadratic Time)
This approach uses dynamic programming to solve the problem. We define a function `dp(k, n)` which represents the minimum number of moves required to determine the critical floor `f` with `k` eggs and `n` floors. The goal is to find `dp(K, N)` by building a DP table.
**Time:** O(k * n^2). We have three nested loops: `k` eggs, `n` floors, and a linear scan of `n` possible drop floors. · **Space:** O(k * n) for the 2D DP table.
**Pros:** Conceptually straightforward application of dynamic programming.; Correctly solves the problem by exploring all possibilities.
**Cons:** The time complexity is too high for the given constraints (`n` up to 10000), leading to a "Time Limit Exceeded" error on most platforms.
### Explanation
Let `dp[i][j]` be the minimum number of moves needed for `i` eggs and `j` floors.
When we drop an egg from floor `x` (where `1 <= x <= j`), there are two outcomes:
1.  **The egg breaks**: We have `i-1` eggs left and need to check the `x-1` floors below. The number of moves required is `dp[i-1][x-1]`.
2.  **The egg survives**: We still have `i` eggs and need to check the `j-x` floors above. The number of moves required is `dp[i][j-x]`.

Since we need to find the solution for the worst-case scenario, the number of moves for a drop from floor `x` is `1 + max(dp[i-1][x-1], dp[i][j-x])`.
To find the minimum moves for `j` floors, we must choose the floor `x` that minimizes this worst-case value.
This leads to the recurrence relation: `dp[i][j] = 1 + min_{1 <= x <= j} { max(dp[i-1][x-1], dp[i][j-x]) }`.

**Base Cases**:
- `dp[i][0] = 0` (0 floors, 0 moves).
- `dp[1][j] = j` (1 egg, `j` floors, we must check linearly from floor 1 to `j`).

We can build a 2D DP table of size `(k+1) x (n+1)` to store the results and compute them iteratively.

```java
class Solution {
    public int superEggDrop(int k, int n) {
        int[][] dp = new int[k + 1][n + 1];
        for (int j = 1; j <= n; j++) {
            dp[1][j] = j;
        }
        for (int i = 1; i <= k; i++) {
            dp[i][0] = 0;
        }

        for (int i = 2; i <= k; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = Integer.MAX_VALUE;
                for (int x = 1; x <= j; x++) {
                    int moves = 1 + Math.max(dp[i - 1][x - 1], dp[i][j - x]);
                    dp[i][j] = Math.min(dp[i][j], moves);
                }
            }
        }
        return dp[k][n];
    }
}
```
### Algorithm
- Create a 2D array `dp` of size `(k+1) x (n+1)`.
- Initialize base cases: `dp[i][0] = 0` for all `i`, and `dp[1][j] = j` for all `j`.
- Iterate for eggs `i` from 2 to `k`.
- Iterate for floors `j` from 1 to `n`.
- Inside this loop, iterate for the drop floor `x` from 1 to `j`.
- Calculate `moves = 1 + max(dp[i-1][x-1], dp[i][j-x])`.
- Update `dp[i][j] = min(dp[i][j], moves)`.
- The final answer is `dp[k][n]`.

## Dynamic Programming with Binary Search
This approach improves upon the previous DP solution. We observe that in the recurrence `dp[i][j] = 1 + min_{1 <= x <= j} { max(dp[i-1][x-1], dp[i][j-x]) }`, the term `dp[i-1][x-1]` is monotonically increasing with `x`, while `dp[i][j-x]` is monotonically decreasing with `x`. This property allows us to use binary search to find the optimal drop floor `x`.
**Time:** O(k * n * log n). The two outer loops run in `O(k*n)` and the inner binary search takes `O(log n)`. · **Space:** O(k * n) for the 2D DP table.
**Pros:** Significantly faster than the quadratic approach.; Passes more test cases and is often sufficient for medium constraints.
**Cons:** The time complexity can still be a bottleneck for the largest constraints.; Space complexity is still high at O(k * n).
### Explanation
The state and recurrence relation are the same as the previous approach. The key insight is to optimize the search for the optimal drop floor `x`.
Let `f1(x) = dp[i-1][x-1]` (increasing) and `f2(x) = dp[i][j-x]` (decreasing). We want to find `min(max(f1(x), f2(x)))`.
The minimum of the maximum of an increasing and a decreasing function occurs where they are closest, i.e., near their intersection point.
Instead of a linear scan for `x` from 1 to `j`, we can use binary search to find the optimal `x` that minimizes `max(f1(x), f2(x))`.
For a given `mid` in the binary search (representing the drop floor `x`), we compare `dp[i-1][mid-1]` and `dp[i][j-mid]`.
- If `dp[i-1][mid-1] < dp[i][j-mid]`, the intersection point is to the right, so we search in the range `[mid+1, high]`.
- If `dp[i-1][mid-1] > dp[i][j-mid]`, the intersection point is to the left, so we search in the range `[low, mid-1]`.
This optimization reduces the time to find the optimal `x` from `O(j)` to `O(log j)`.

```java
class Solution {
    public int superEggDrop(int k, int n) {
        int[][] dp = new int[k + 1][n + 1];
        for (int j = 1; j <= n; j++) {
            dp[1][j] = j;
        }

        for (int i = 2; i <= k; i++) {
            for (int j = 1; j <= n; j++) {
                int low = 1, high = j;
                int result = j;
                while (low <= high) {
                    int mid = low + (high - low) / 2;
                    int breakCase = dp[i - 1][mid - 1];
                    int noBreakCase = dp[i][j - mid];
                    int moves = 1 + Math.max(breakCase, noBreakCase);
                    result = Math.min(result, moves);

                    if (breakCase > noBreakCase) {
                        high = mid - 1;
                    } else {
                        low = mid + 1;
                    }
                }
                dp[i][j] = result;
            }
        }
        return dp[k][n];
    }
}
```
### Algorithm
- Create a 2D array `dp` of size `(k+1) x (n+1)`.
- Initialize base cases: `dp[i][0] = 0` and `dp[1][j] = j`.
- Iterate for eggs `i` from 2 to `k`.
- Iterate for floors `j` from 1 to `n`.
- Inside this loop, use binary search on `x` (from `low=1` to `high=j`) to find the minimum value of `1 + max(dp[i-1][x-1], dp[i][j-x])`.
- Store this minimum value in `dp[i][j]`.
- The final answer is `dp[k][n]`.

## Alternative DP Formulation (Optimal)
This approach rephrases the problem. Instead of asking "what is the minimum number of moves for `k` eggs and `n` floors?", we ask "what is the maximum number of floors we can check with `k` eggs and `m` moves?". This change of perspective leads to a more efficient solution.
**Time:** O(k * m) where `m` is the final answer (number of moves). In the worst case, `m` can be up to `n` (when `k=1`), so the complexity is `O(k * n)`. However, `m` is much smaller than `n` for larger `k`. Specifically, `m` is approximately `O(log n)` when `k` is large enough (`k > log2(n)`), making the complexity closer to `O(k * log n)`. The overall upper bound is `O(k*n)`. · **Space:** O(k) for the 1D DP array.
**Pros:** This is the most efficient approach in terms of both time and space complexity.; The logic is elegant once the problem is rephrased.
**Cons:** The change in perspective from the original problem statement might not be immediately obvious.
### Explanation
Let `dp[m][k]` be the maximum number of floors we can check with `m` moves and `k` eggs.
If we make a move by dropping an egg from some floor `x`, there are two outcomes:
1.  **Egg breaks**: We have `m-1` moves and `k-1` eggs left. We can check `dp[m-1][k-1]` floors below `x`.
2.  **Egg survives**: We have `m-1` moves and `k` eggs left. We can check `dp[m-1][k]` floors above `x`.

Therefore, the total number of floors we can check is the sum of floors below `x`, floor `x` itself, and floors above `x`.
This gives the recurrence relation: `dp[m][k] = 1 + dp[m-1][k-1] + dp[m-1][k]`.
Our goal is to find the smallest number of moves `m` such that `dp[m][k] >= n`.
We can compute `dp[m][k]` for increasing `m` (moves) starting from 1, until `dp[m][k]` is large enough to cover all `n` floors.

**Space Optimization**: Notice that `dp[m][k]` only depends on the values from the previous number of moves, `m-1`. This means we can optimize the space from a 2D array `O(m*k)` to a 1D array `O(k)`. The recurrence becomes `dp[k] = 1 + dp_previous[k-1] + dp_previous[k]`.

```java
class Solution {
    public int superEggDrop(int k, int n) {
        // dp[j] will be the max floors we can check with j eggs and `moves` moves.
        int[] dp = new int[k + 1];
        int moves = 0;
        while (dp[k] < n) {
            moves++;
            // Iterate backwards to use results from the previous move count
            for (int j = k; j > 0; j--) {
                // dp[j] (new) = 1 (current floor) + dp[j] (old, for no-break) + dp[j-1] (old, for break)
                dp[j] = 1 + dp[j] + dp[j - 1];
            }
        }
        return moves;
    }
}
```
### Algorithm
- Create a 1D array `dp` of size `k+1` to store the maximum floors checkable for the current number of moves. Initialize it to zeros.
- Initialize `moves = 0`.
- Start a loop that continues as long as `dp[k] < n`.
- Inside the loop, increment `moves`.
- Update the `dp` array for the current number of `moves`. Iterate `j` from `k` down to 1. The backward iteration is crucial to use the `dp` values from the *previous* move count.
- The update rule is `dp[j] = 1 + dp[j] + dp[j-1]`.
- Once the loop terminates (i.e., `dp[k] >= n`), the value of `moves` is the minimum number of moves required.

# Solutions
### Java

```java
class Solution {
private
  int[][] f;
public
  int superEggDrop(int k, int n) {
    f = new int[n + 1][k + 1];
    return dfs(n, k);
  }
private
  int dfs(int i, int j) {
    if (i < 1) {
      return 0;
    }
    if (j == 1) {
      return i;
    }
    if (f[i][j] != 0) {
      return f[i][j];
    }
    int l = 1, r = i;
    while (l < r) {
      int mid = (l + r + 1) >> 1;
      int a = dfs(mid - 1, j - 1);
      int b = dfs(i - mid, j);
      if (a <= b) {
        l = mid;
      } else {
        r = mid - 1;
      }
    }
    return f[i][j] = Math.max(dfs(l - 1, j - 1), dfs(i - l, j)) + 1;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int superEggDrop(int k, int n) {
    int f[n + 1][k + 1];
    memset(f, 0, sizeof(f));
    function<int(int, int)> dfs = [&](int i, int j) -> int {
      if (i < 1) {
        return 0;
      }
      if (j == 1) {
        return i;
      }
      if (f[i][j]) {
        return f[i][j];
      }
      int l = 1, r = i;
      while (l < r) {
        int mid = (l + r + 1) >> 1;
        int a = dfs(mid - 1, j - 1);
        int b = dfs(i - mid, j);
        if (a <= b) {
          l = mid;
        } else {
          r = mid - 1;
        }
      }
      return f[i][j] = max(dfs(l - 1, j - 1), dfs(i - l, j)) + 1;
    };
    return dfs(n, k);
  }
};

```

### Python

```python
class Solution:
    def superEggDrop(self, k: int, n: int) -> int: @ cache def dfs(i: int, j: int) -> int: if i < 1: return 0 if j == 1: return i l, r = 1, i while l < r: mid = (l + r + 1) >> 1 a = dfs(mid - 1, j - 1) b = dfs(i - mid, j) if a <= b: l = mid else: r = mid - 1 return max(dfs(l - 1, j - 1), dfs(i - l, j)) + 1 return dfs(n, k)

```