Egg Drop With 2 Eggs And N Floors - Leetcode Solution

Problem:

You are given two identical eggs and you have access to a building with n floors labeled from 1 to n.

You also have a function called drop that takes an integer input of a floor and returns:

0 if the egg does not break on that floor 1 if the egg breaks on that floor You have to use the eggs to find the minimum number of floors it will take to determine with certainty the value of f such that 0 <= f <= n.

Approach:

This problem belongs to dynamic programming and can be solved via memoization technique.

We need to first create a matrix memo of dimensions n+1 and 3+1.

Here, memo[i][j] represents the minimum number of moves needed to determine the value of f when we have i floors to work with and j eggs.

At first, we need to fill the first row in which we have only one egg. So, we will fill the matrix as follows:

memo[1][1] = 1 memo[2][1] = 2 memo[3][1] = 3 . . . memo[n][1] = n

For eg: When we have only one egg and i floors, we start dropping the egg from 1st floor, then 2nd and so on till we find a floor from which egg broke. Hence, the minimum number of moves will be equal to the number of floors we have in this case.

Now, we have to consider the second egg. We can't use the same approach we did for the first egg. If we start from the first floor and move up floor by floor, it will take a lot of time and we might run out of eggs before finding out the floor f. So, we need a better approach.

If we drop an egg from a given floor, then there are two possibilities:

Case 1: The egg breaks and we are left with j-1 eggs to test for the remaining i-1 floors below that floor. Case 2: The egg does not break and we have j eggs to test for the remaining floors above the current floor.

So, if we drop an egg from a certain floor, then the minimum number of moves required will be equal to the maximum of the following:

1. 1 + memo[i - 1][j - 1] (If the egg breaks, check from floors 1 to i-1, and i-1 floors remain with j-1 eggs)
2. 1 + memo[n - i][j](If the egg does not break, check from floors i+1 to n, and upper (n-i) floors remain with j eggs)

We have to take the minimum number of moves as we want to minimize the worst case and find the value of f with certainty.

Solution:

class Solution: def twoEggDrop(self, n: int) -> int:

    memo = [[float('inf') for j in range(4)] for i in range(n + 1)]
    
    #filling the first column
    for i in range(n+1):
        memo[i][1] = i
        
    #filling the first row
    for i in range(1,4):
        memo[1][i] = 1
    
    for i in range(2,n+1):
        for j in range(2,4):
            for k in range(1,i):
                memo[i][j] = min(memo[i][j], 1+max(memo[k-1][j-1],memo[i-k][j]))
    
    return memo[n][2]  #returning minimum number of moves with 2 eggs and n floors.
    

Time Complexity: O(n^2) Space Complexity: O(n * 4)

1