Minimum Egg Drops Editorial

Practice Problem Link: Minimum Egg Drops 

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

You have k eggs and a building with n floors (labeled 1 to n). There exists a floor f (0 <= f <= n) on the building such that any egg dropped from a floor higher than f will break and, any egg dropped at or below f won't break. Each move you can take an unbroken egg and drop if from any floor x (1 <= x <= n). Find the minimum number of moves that you need to determine with certainty what the value of f is.

Naive Approach

The brute force approach to this problem is to use recursion. We can try to drop an egg from every possible floor and try to calculate the minimum number of egg drops needed in the worst-case through recursion. The floor, that gives the least possible value in the worst-case scenario will be a part of the solution. The key thing to think about in this problem is that when an egg is dropped from the nth floor, the egg will either break, or not break, depending upon which we can implement the cases of our recursion.

Analysis

• Time Complexity: Exponential
• Space Complexity: O(1) if recursion stack memory is excluded.

Implementation

C++

int minEggDrops(int eggs, int floors) {
	if(floors <= 1 || eggs == 1) {
		return floors;
	}
	int minimum = INT_MAX, result;
	for(int i = 1; i <= floors; i++)
		result = max(minEggDrops(eggs - 1, i - 1), minEggDrops(eggs, floors - i));
		minimum = min(result, minimum);
	}
	return minimum + 1;
}
int minimumMoves(int k, int n) {
    return minEggDrops(k, n);
}

Java

class Solution {
	int minEggDrops(int eggs, int floors) {
		if(floors <= 1 || eggs == 1) {
			return floors;
		}
		int minimum = Integer.MAX_VALUE, result;
		for(int i = 1; i <= floors; i++) {
			result = Math.max(minEggDrops(eggs - 1, i - 1), minEggDrops(eggs, floors - i));
			minimum = Math.min(result, minimum);
		}
		return minimum + 1;
	}
	int minimumMoves(int k, int n) {
	    return minEggDrops(k, n);
	}
}

Optimal Approach

We can observe that in the naive approach, many of the function calls are being repeated again and again. So, we can tabulate those values with a Dynamic Programming approach, with a 2D DP matrix, where rows will represent the eggs and columns will represent the floors, and DP[i][j] will store the optimal answer for i eggs and j floors. 

Analysis

• Time Complexity: O(n * n * k)
• Space Complexity: O(n * k)

Implementation

C++

vector<vector<int>> dp;
int minEggDrops(int eggs, int floors) {
	if(floors <= 1 || eggs == 1) {
		return dp[eggs][floors] = floors;
	}
	if(dp[eggs][floors] != -1) {
		return dp[eggs][floors];
	}
	int minimum = INT_MAX, result;
	for(int i = 1; i <= floors; i++) {
		result = max(minEggDrops(eggs - 1, i - 1), minEggDrops(eggs, floors - i));
		minimum = min(result, minimum);
	}
	return dp[eggs][floors] = minimum + 1;
}
int minimumMoves(int k, int n) {
	vector<vector<int>> temp(k + 1, vector<int> (n + 1, -1));
	dp = temp;
    return minEggDrops(k, n);
}

Java

class Solution {
	int dp[][];
	int minEggDrops(int eggs, int floors) {
		if(floors <= 1 || eggs == 1) {
			return dp[eggs][floors] = floors;
		}
		if(dp[eggs][floors] != -1) {
			return dp[eggs][floors];
		}
		int minimum = Integer.MAX_VALUE, result;
		for(int i = 1; i <= floors; i++) {
			result = Math.max(minEggDrops(eggs - 1, i - 1), minEggDrops(eggs, floors - i));
			minimum = Math.min(result, minimum);
		}
		return dp[eggs][floors] = minimum + 1;
	}
	int minimumMoves(int k, int n) {
		dp = new int[k + 1][n + 1];
		for(int i = 0; i <= k; i++) {
			Arrays.fill(dp[i], -1);
		}
	    return minEggDrops(k, n);
	}
}

Bottom-Up Implementation

int minimumMoves(int k, int n) {
	int dp[k + 1][n + 1];
	int result = 0;
	for(int i = 1; i <= k; i++) {
		for(int j = 0; j < 2; j++) {
			dp[i][j] = j;
		}
	}
	for(int j = 1; j <= n; j++) {
		dp[1][j] = j;
	}
	for(int i = 2; i <= k; i++) {
		for(int j = 2; j <= n; j++) {
			dp[i][j] = INT_MAX;
			for(int l = 1; l <= j; l++) {
				result = max(dp[i - 1][l - 1], dp[i][j - l]) + 1;
				dp[i][j] = min(dp[i][j], result);
			}
		}
	}
	return dp[k][n];
}

Java

class Solution {
	int minimumMoves(int k, int n) {
		int[][] dp = new int[k + 1][n + 1];
		int result = 0;
		for(int i = 1; i <= k; i++) {
			for(int j = 0; j < 2; j++) {
				dp[i][j] = j;
			}
		}
		for(int j = 1; j <= n; j++) {
			dp[1][j] = j;
		}
		for(int i = 2; i <= k; i++) {
			for(int j = 2; j <= n; j++) {
				dp[i][j] = Integer.MAX_VALUE;
				for(int l = 1; l <= j; l++) {
					result = Math.max(dp[i - 1][l - 1], dp[i][j - l]) + 1;
					dp[i][j] = Math.min(dp[i][j], result);
				}
			}
		}
		return dp[k][n];
	}
}