Super Egg Drop Hard 0 attempts
LeetCode ↗

Super Egg Drop

Hard Dynamic ProgrammingMemoization LeetCode

You have k identical eggs and a building with n floors. There is an unknown highest safe floor f in [0, n]: an egg survives at floors at or below f and breaks above f. A broken egg cannot be reused. Determine the minimum number of drops needed in the worst case to identify f, including the possibilities that every floor is safe or no floor is safe.

Input Format
Implement superEggDrop(k, n). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 ยท Run Sample

Input
k = 2
n = 6
Output
3

Example 2

Input
k = 1
n = 2
Output
2
Constraints
  • 1 <= k <= 100
  • 1 <= n <= 10^4
Test Cases (2)
Case 1
Args: [2,6] Expected: 3
Case 2
Args: [1,2] Expected: 2
Topics
Dynamic ProgrammingMemoization

DP: Moves-based approach

dp[m][k] = max floors checkable with m moves and k eggs.

javascript
function superEggDrop(k, n) {
  const dp = Array.from({length:n+1}, ()=>Array(k+1).fill(0));
  let m = 0;
  while (dp[m][k] < n) {
    m++;
    for (let j = 1; j <= k; j++) dp[m][j] = dp[m-1][j-1] + dp[m-1][j] + 1;
  }
  return m;
}

Time: O(kn) | Space: O(kn)

Saved in this browser only. Private to you.

JavaScript