1884. Egg Drop With 2 Eggs and N Floors

Problem Explanation:

In this problem, we are given two identical eggs and a building with n floors (numbered 1 to n). We must find the 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. The goal is to find the minimum number of moves required to determine the value of f with certainty. To solve this problem, we'll be using dynamic programming.

Let's work through an example:

Example

1
2
3Input: n = 2
4Output: 2

For this example, we have 2 floors. We can drop the first egg from floor 1 and the second egg from floor 2:

If the first egg breaks, we know that f = 0.
If the second egg breaks but the first egg didn’t, we know that f = 1.
Otherwise, if both eggs survive, we know that f = 2.

We only needed 2 moves to determine the value of f, so the output is 2.

Solution Approach

The solution approach for this problem includes using dynamic programming and a 2D array dp with n + 1 rows and 2 columns, where dp[i][j] represents the minimum number of moves required to determine the value of f with i floors and j + 1 eggs. We will loop over all possible values of j and get the minimum possible value of dp[i][1].

Algorithm Steps

Create a 2D array dp with n+1 rows and 2 columns.
Set dp[i][0] = i for all 0 <= i <= n.
Set dp[1][1] = 1 for a single floor.
For 2 <= i <= n, if the previous egg was dropped from floor j (1 <= j < i), then dp[i][1] = max(dp[j - 1][0], dp[i - j][1]) + 1.
Loop over all possible values of j and get the minimum possible value of dp[i][1].
Finally, return dp[n][1].

Python Solution

1
2python
3class Solution:   
4    def twoEggDrop(self, n: int) -> int:
5        def drop(k: int, N: int) -> int:
6            if k == 0:
7                return 0
8            if k == 1:
9                return N
10            if N == 0:
11                return 0
12            if N == 1:
13                return 1
14            if dp[k][N] != -1:
15                return dp[k][N]
16            
17            l, r = 1, N + 1
18
19            while l < r:
20                m = (l + r) // 2
21                broken = drop(k - 1, m - 1)
22                unbroken = drop(k, N - m)
23                if broken >= unbroken:
24                    r = m
25                else:
26                    l = m + 1
27
28            dp[k][N] = 1 + drop(k - 1, l - 1)
29            return dp[k][N]
30
31        dp = [[-1] * (n + 1) for _ in range(3)]
32        return drop(2, n)

Java Solution

1
2java
3class Solution {
4    public int twoEggDrop(int n) {
5        int[][] dp = new int[3][n + 1];
6
7        for (int i = 0; i <= n; i++) {
8            dp[0][i] = 0;
9            dp[1][i] = i;
10            dp[2][i] = -1;
11        }
12
13        for (int i = 1; i <= n; i++) {
14            int minMoves = Integer.MAX_VALUE;
15            for (int j = 1; j < i; j++) {
16                int moves = Math.max(dp[0][j - 1], dp[1][i - j]) + 1;
17                minMoves = Math.min(minMoves, moves);
18            }
19            dp[2][i] = minMoves;
20
21            if (dp[1][i] == dp[2][i]) {
22                break;
23            }
24
25            dp[1][i] = dp[2][i];
26        }
27
28        return dp[2][n];
29    }
30}

JavaScript Solution

1
2javascript
3class Solution {
4    twoEggDrop(n) {
5        const dp = Array.from({length: 3}, () => Array(n + 1).fill(-1));
6
7        for (let i = 0; i <= n; i++) {
8            dp[0][i] = 0;
9            dp[1][i] = i;
10        }
11
12        for (let i = 1; i <= n; i++) {
13            dp[2][i] = dp[1][i];
14            for (let j = 1; j < i; j++) {
15                const moves = Math.max(dp[0][j - 1], dp[1][i - j]) + 1;
16                dp[2][i] = Math.min(dp[2][i], moves);
17            }
18
19            if (dp[1][i] === dp[2][i]) {
20                break;
21            }
22
23            dp[1][i] = dp[2][i];
24        }
25
26        return dp[2][n];
27    }
28}

C++ Solution

1
2cpp
3class Solution {
4public:
5    int twoEggDrop(int n) {
6        vector<vector<int>> dp(3, vector<int>(n + 1, -1));
7
8        for (int i = 0; i <= n; i++) {
9            dp[0][i] = 0;
10            dp[1][i] = i;
11        }
12
13        for (int i = 1; i <= n; i++) {
14            dp[2][i] = dp[1][i];
15            for (int j = 1; j < i; j++) {
16                int moves = max(dp[0][j - 1], dp[1][i - j]) + 1;
17                dp[2][i] = min(dp[2][i], moves);
18            }
19
20            if (dp[1][i] == dp[2][i]) {
21                break;
22            }
23
24            dp[1][i] = dp[2][i];
25        }
26
27        return dp[2][n];
28    }
29};

C# Solution

1
2csharp
3public class Solution {
4    public int TwoEggDrop(int n) {
5        int[][] dp = new int[3][];
6        for (int i = 0; i < 3; i++) {
7            dp[i] = new int[n + 1];
8        }
9
10        for (int i = 0; i <= n; i++) {
11            dp[0][i] = 0;
12            dp[1][i] = i;
13            dp[2][i] = -1;
14        }
15
16        for (int i = 1; i <= n; i++) {
17            int minMoves = int.MaxValue;
18            for (int j = 1; j < i; j++) {
19                int moves = Math.Max(dp[0][j - 1], dp[1][i - j]) + 1;
20                minMoves = Math.Min(minMoves, moves);
21            }
22            dp[2][i] = minMoves;
23
24            if (dp[1][i] == dp[2][i]) {
25                break;
26            }
27
28            dp[1][i] = dp[2][i];
29        }
30
31        return dp[2][n];
32    }
33}

In the solutions above, the logic behind the code in each language is explained step-by-step in the algorithm steps section, as we perform dynamic programming to build up the dp array and find the minimum number of moves required to determine the value of f.The solutions above for Python, Java, JavaScript, C++, and C# define the standard dynamic programming method for solving the egg drop problem with two eggs and n floors. These solutions have a time complexity of O(n^2) and O(n) space complexity. You can try implementing the given solutions in your preferred programming language to understand how to solve this problem effectively.

By following the algorithm steps mentioned above and analyzing the code provided for each language, we can better understand the process of problem-solving using dynamic programming. This helps us break down complex problems into simpler sub-problems and solve them in a systematic manner for efficient solutions. Besides, practicing with multiple languages will help you become a better programmer in general, as it strengthens your ability to adapt and learn different programming paradigms.

In conclusion, the egg drop problem is a classic question in dynamic programming that can be solved using various techniques. The methods provided above are well-explained and optimized to solve this problem for given constraints. Implementing the solutions in different programming languages will help you enhance your programming skills and strengthen your understanding of dynamic programming concepts.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don’t know