Problem

Koko loves to eat bananas. There are n piles of bananas, the ith pile has piles[i] bananas. The guards have gone and will come back in h hours.

Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour.

Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.

Return the minimum integer k such that she can eat all the bananas within h hours.

Examples

Example 1:

Input: piles = [3,6,7,11], h = 8
Output: 4

Example 2:

Input: piles = [30,11,23,4,20], h = 5
Output: 30

Example 3:

Input: piles = [30,11,23,4,20], h = 6
Output: 23

Who is Koko

[!NOTE] Fun Fact Koko is a well-known name associated with a famous gorilla 🦍, not an elephant 🐘 or a monkey 🐵. Koko, the gorilla, was known for her ability to communicate using sign language. She was the subject of a long-term psychological and linguistic study and became famous for her vocabulary and understanding of American Sign Language (ASL).

Solution

We know Koko eats k bananas from a pile. So, if guard is gone for h hours, number of piles will be less than equal to h.

Method 1 - Binary Search

Let’s understand the solution, as we are going to be using Binary Search we have given an Array [3,6,7,11] And we have to eat every single pile of bananas in less than or equals to hours h = 8.

Initialize the bounds

  • The minimum possible eating speed (low) is 1 banana per hour.
  • The maximum possible eating speed (high) is the maximum number of bananas in any single pile. This is because, in the worst case, Koko might need to eat an entire pile in one hour. In above example, high = 11

We go in the middle - and see if that is the right speed to eat bananas per hour, i.e. k. We search in range [low, high], hence we go through all the values in this range.

Iteration 1
piles = [3,6,7,11], h = 8

low = 1, high = 11 => mid = 12 / 2 = 6

Can Koko eat all bananas in 8 hours with eating speed = 6
hoursNeeded = 1 + 1 + 2 + 2 = 6

Koko can eat all bananas in 6 hours instead of 8, so it needs to slow down.
high = mid - 1 = 5
Iteration 2
piles = [3,6,7,11], h = 8

low = 1, high = 5 => mid = 12 / 2 = 3

Can Koko eat all bananas in 8 hours with eating speed = 3
hoursNeeded = 1 + 2 + 3 + 4 = 10

Koko cannot eat all bananas in 10 hours which is more than 8 hours, so it needs to speed up.
low = mid + 1 = 4
Iteration 2
piles = [3,6,7,11], h = 8

low = 4, high = 5 => mid = 9 / 2 = 4

Can Koko eat all bananas in 8 hours with eating speed = 4
hoursNeeded = 1 + 2 + 2 + 3 = 8

Koko can eat all bananas in 8 hours instead of 8, but can it eat at even slower speed and still match the target
high = mid - 1 = 3
Iteration 3
piles = [3,6,7,11], h = 8

low = 4, high = 3 => We have got the best possible answer

Code

We can also use low = 1 and high = 10^9 because those are the constraints.

Java
public class Solution {

	public int minEatingSpeed(int[] piles, int h) {
		int low = 1; // Minimum possible eating speed
		int high = Arrays.stream(piles).max().getAsInt(); // Maximum possible eating speed
		while (low <= high) {
			int mid = low + (high - low) / 2;

			if (catEatInTime(piles, h, mid)) {
				high = mid - 1; // Try for a smaller eating speed
			} else {
				low = mid + 1; // Increase the eating speed
			}
		}

		return low; // or high, since they will converge
	}

	private boolean catEatInTime(int[] piles, int h, int k) {
		int hoursNeeded = 0;

		for (int pile: piles) {
			hoursNeeded += (pile + k - 1) / k; // Same as Math.ceil((double)pile / k)
			// We can also do - 
			if (hoursNeeded > h) {
				return false; // More hours needed than allowed
			}
		}

		return true; // Possible to eat all bananas within the given hours
	}
}

We can also do following for line 23:

			int div = pile / k;
			hoursNeeded += div;
			if (pile % k != 0) {
				hoursNeeded++;
			}

Complexity

  • ⏰ Time complexity: O(logM * n), where M is the max value in piles, and n is length of piles array. For logM times, we run catEatInTime which takes O(n) time.
  • 🧺 Space complexity: O(1)