887. Super Egg Drop LeetCode Solution

Last updated: February 20, 2025

In this guide, you will get 887. Super Egg Drop LeetCode Solution with the best time and space complexity. The solution to Super Egg Drop problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Super Egg Drop solution in C++
Super Egg Drop solution in Java
Super Egg Drop solution in Python
Additional Resources

887. Super Egg Drop LeetCode Solution image

Problem Statement of Super Egg Drop

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

Complexity Analysis

Time Complexity: O(kn^2)
Space Complexity: O(kn)

887. Super Egg Drop LeetCode Solution in C++

class Solution {
 public:
  int superEggDrop(int k, int n) {
    vector<vector<int>> mem(k + 1, vector<int>(n + 1, INT_MAX));
    return drop(k, n, mem);
  }

 private:
  // Returns the minimum number of moves to know f with k eggs and n floors.
  int drop(int k, int n, vector<vector<int>>& mem) {
    if (k == 0)  // no eggs -> done
      return 0;
    if (k == 1)  // one egg -> drop from 1-th floor to n-th floor
      return n;
    if (n == 0)  // no floor -> done
      return 0;
    if (n == 1)  // one floor -> drop from that floor
      return 1;
    if (mem[k][n] != INT_MAX)
      return mem[k][n];

    for (int i = 1; i <= n; ++i) {
      const int broken = drop(k - 1, i - 1, mem);
      const int unbroken = drop(k, n - i, mem);
      mem[k][n] = min(mem[k][n], 1 + max(broken, unbroken));
    }

    return mem[k][n];
  }
};
/* code provided by PROGIEZ */

887. Super Egg Drop LeetCode Solution in Java

class Solution {
  public int superEggDrop(int k, int n) {
    int[][] mem = new int[k + 1][n + 1];
    Arrays.stream(mem).forEach(A -> Arrays.fill(A, Integer.MAX_VALUE));
    return drop(k, n, mem);
  }

  // Returns the minimum number of moves to know f with k eggs and n floors.
  private int drop(int k, int n, int[][] mem) {
    if (k == 0) // no eggs -> done
      return 0;
    if (k == 1) // one egg -> drop from 1st floor to nth floor
      return n;
    if (n == 0) // no floor -> done
      return 0;
    if (n == 1) // one floor -> drop from that floor
      return 1;
    if (mem[k][n] != Integer.MAX_VALUE)
      return mem[k][n];

    for (int i = 1; i <= n; ++i) {
      final int broken = drop(k - 1, i - 1, mem);
      final int unbroken = drop(k, n - i, mem);
      mem[k][n] = Math.min(mem[k][n], 1 + Math.max(broken, unbroken));
    }

    return mem[k][n];
  }
}
// code provided by PROGIEZ

887. Super Egg Drop LeetCode Solution in Python

class Solution {
 public:
  int superEggDrop(int k, int n) {
    vector<vector<int>> mem(k + 1, vector<int>(n + 1, -1));
    return drop(k, n, mem);
  }

 private:
  // Returns the minimum number of moves to know f with k eggs and n floors.
  int drop(int k, int n, vector<vector<int>>& mem) {
    if (k == 0)  // no eggs -> done
      return 0;
    if (k == 1)  // one egg -> drop from 1-th floor to n-th floor
      return n;
    if (n == 0)  // no floor -> done
      return 0;
    if (n == 1)  // one floor -> drop from that floor
      return 1;
    if (mem[k][n] != -1)
      return mem[k][n];

    //   broken[i] := drop(k - 1, i - 1) is increasing with i
    // unbroken[i] := drop(k,     n - i) is decreasing with i
    // mem[k][n] := 1 + min(max(broken[i], unbroken[i])), 1 <= i <= n
    // Find the first index i s.t broken[i] >= unbroken[i], which minimizes
    // max(broken[i], unbroken[i]).

    int l = 1;
    int r = n + 1;

    while (l < r) {
      const int m = (l + r) / 2;
      const int broken = drop(k - 1, m - 1, mem);
      const int unbroken = drop(k, n - m, mem);
      if (broken >= unbroken)
        r = m;
      else
        l = m + 1;
    }

    return mem[k][n] = 1 + drop(k - 1, l - 1, mem);
  }
};
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents