Egg Dropping Problem

Problem Statement

You are given n eggs and a building with k floors. You need to find the minimum number of trials (drops) required in the worst case to determine the critical floor — the highest floor from which an egg can be dropped without breaking.

Example:

• Input: n = 2, k = 10
• Output: 4 (With 2 eggs and 10 floors, the worst case needs 4 trials)

Noob-Friendly Explanation

Imagine you're in a tall building and you have some eggs. You want to find out the highest floor from which you can drop an egg without it breaking. If you had infinite eggs, you'd just do binary search. But eggs are limited! If an egg breaks, it's gone. If it doesn't break, you can reuse it. You want a strategy that finds the answer in the fewest drops possible, even in the worst case scenario. It's like a game where you're trying to be as efficient as possible while being careful with your limited eggs.

Approach 1: Brute Force

Intuition

Try every floor as a potential drop point. If the egg breaks, search below with one fewer egg. If it doesn't break, search above with the same number of eggs. Take the minimum over all floors of the worst case (maximum of break/no-break).

Algorithm

1. Base cases: 0 or 1 floors need 0 or 1 trial; 1 egg needs k trials.
2. For each floor from 1 to k, recursively compute trials for break and no-break cases.
3. Take the worst case (max) for each floor, then the best choice (min) across all floors.

class Solution {
    public static int eggDropBrute(int n, int k) {
        // Base cases
        if (k == 0 || k == 1) return k;
        if (n == 1) return k;

        int minTrials = Integer.MAX_VALUE;

        for (int floor = 1; floor <= k; floor++) {
            // Egg breaks: search below with n-1 eggs
            int breaks = eggDropBrute(n - 1, floor - 1);
            // Egg survives: search above with n eggs
            int survives = eggDropBrute(n, k - floor);

            // Worst case for this floor choice
            int worstCase = 1 + Math.max(breaks, survives);
            minTrials = Math.min(minTrials, worstCase);
        }

        return minTrials;
    }

    public static void main(String[] args) {
        System.out.println(eggDropBrute(2, 10)); // Output: 4
    }
}

Complexity Analysis

• Time Complexity: O(n * 2^k) - exponential due to overlapping subproblems
• Space Complexity: O(n + k) - recursion stack depth

Approach 2: Optimal

Intuition

Use a 2D DP table where dp[i][j] represents the minimum number of trials needed with i eggs and j floors. Fill the table bottom-up using the same recurrence as brute force.

Algorithm

1. Create a 2D array dp[n+1][k+1].
2. Base cases: dp[i][0] = 0, dp[i][1] = 1, dp[1][j] = j.
3. For each cell, try every floor and pick the one that gives the minimum worst case.
4. Return dp[n][k].

class Solution {
    public static int eggDrop(int n, int k) {
        int[][] dp = new int[n + 1][k + 1];

        // Base cases
        for (int i = 1; i <= n; i++) {
            dp[i][0] = 0; // 0 floors need 0 trials
            dp[i][1] = 1; // 1 floor needs 1 trial
        }
        for (int j = 1; j <= k; j++) {
            dp[1][j] = j; // 1 egg needs j trials for j floors
        }

        // Fill the rest of the table
        for (int i = 2; i <= n; i++) {
            for (int j = 2; j <= k; j++) {
                dp[i][j] = Integer.MAX_VALUE;
                for (int floor = 1; floor <= j; floor++) {
                    int breaks = dp[i - 1][floor - 1];
                    int survives = dp[i][j - floor];
                    int worstCase = 1 + Math.max(breaks, survives);
                    dp[i][j] = Math.min(dp[i][j], worstCase);
                }
            }
        }

        return dp[n][k];
    }

    public static void main(String[] args) {
        System.out.println(eggDrop(2, 10)); // Output: 4
    }
}

Complexity Analysis

• Time Complexity: O(n * k^2) - three nested loops
• Space Complexity: O(n * k) - the 2D dp table