LeetCode Problems

In this tutorial we will solve 875. Koko Eating Bananas from leetcode.

Reference: 875. Koko Eating Bananas

In this problem, we are given `n`

piles of bananas. The `ith`

pile contains `piles[i]`

bananas. We are told that there are some guards, and they have gone away but will return in `h`

hours.

Koko loves to eat bananas. She can choose to eat any number of bananas per hour, and we will denote her eating speed as `k`

bananas per hour. We are also told that Koko likes to eat slowly, but she wants to finish all the bananas. Therefore, we need to find the minimum integer `k`

such that she can eat all the bananas in `h`

hours.

There is also a condition: If Koko's eating speed is `k`

and she picks a pile with fewer than `k`

bananas, she will eat all the bananas in that pile and will not eat any more bananas during that hour.

Watch this video for Binary Search.

Example from leetcode.

```
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
```

```
Constraints:
1 <= piles.length <= 10^4
piles.length <= h <= 10^9
1 <= piles[i] <= 10^9
```

We will use Binary Search to solve this problem.

We need to find the minimum value of `k`

, which represents Koko's banana-eating speed in bananas per hour. The value of `k`

can be a minimum of 1 banana per hour and a maximum of M bananas per hour, where M is the number of bananas in the largest pile.

If we find an eating speed of, say, `b`

bananas per hour that allows Koko to finish all the bananas in `h`

hours, then any speed greater than `b`

will also be valid.

Since we are asked to find the minimum speed, we will search for values less than `b`

until we find `k`

, which is the minimum speed needed to finish all the bananas in `h`

hours.

Similarly, if we find an eating speed of, say, `d`

bananas per hour, and Koko is unable to finish all the bananas in `h`

hours, then any speed less than `d`

will also be invalid. In this case, we need to search for values greater than `d`

until we find `k`

, the minimum speed required to finish all the bananas in `h`

hours.

Let us take example 1 and try to solve it.

```
h = 8
piles = [3, 6, 7, 11]
M = max(piles)
= max([3, 6, 7, 11])
= 11
Therefore, k can be between 1 to 11.
start = 1
end = 11
mid = floor((start + end) / 2)
= floor((1+11)/2)
= 6
let us check if Koko can finish the piles
if the eating speed is k=6 bananas/hour
piles = [3, 6, 7, 11]
t1 = [0, 6, 7, 11] // ate 3 bananas from 1st pile
t2 = [0, 0, 7, 11] // ate 6 bananas from 2nd pile
t3 = [0, 0, 1, 11] // ate 6 bananas from 3rd pile
t4 = [0, 0, 0, 11] // ate 1 banana from 3rd pile
t5 = [0, 0, 0, 5] // ate 6 bananas from 4th pile
t6 = [0, 0, 0, 0] // ate 5 bananas from 4th pile
we can see we are able to eat all the banans in 6 hours.
so, k=6 is one possible eating speed.
also, any value greater than 6 will also be a possible eating speed.
however, we are suppose to look for smaller value so we will shift end.
start = 1
end = 5
mid = floor((start + end) / 2)
= floor((1+5)/2)
= 3
let us check if Koko can finish the piles
if the eating speed is k=3 bananas/hour
piles = [3, 6, 7, 11]
t1 = [0, 6, 7, 11] // ate 3 bananas from 1st pile
t2 = [0, 3, 7, 11] // ate 3 bananas from 2nd pile
t3 = [0, 0, 7, 11] // ate 3 bananas from 2nd pile
t4 = [0, 0, 4, 11] // ate 3 bananas from 3rd pile
t5 = [0, 0, 1, 11] // ate 3 bananas from 3rd pile
t6 = [0, 0, 0, 11] // ate 1 banana from 3rd pile
t7 = [0, 0, 0, 8] // ate 3 bananas from 4th pile
t8 = [0, 0, 0, 5] // ate 3 bananas from 4th pile
we stop here because we have reached 8 hours
and there are still 5 bananas left.
so, k=3 is not a valid eating speed.
we have to find bigger values of k.
start = 4
end = 5
mid = floor((start + end) / 2)
= floor((4+5)/2)
= 4
let us check if Koko can finish the piles
if the eating speed is k=4 bananas/hour
piles = [3, 6, 7, 11]
t1 = [0, 6, 7, 11] // ate 3 bananas from 1st pile
t2 = [0, 2, 7, 11] // ate 4 bananas from 2nd pile
t3 = [0, 0, 7, 11] // ate 2 bananas from 2nd pile
t4 = [0, 0, 3, 11] // ate 4 bananas from 3rd pile
t5 = [0, 0, 0, 11] // ate 3 bananas from 3rd pile
t6 = [0, 0, 0, 7] // ate 4 bananas from 4th pile
t7 = [0, 0, 0, 3] // ate 4 bananas from 4th pile
t8 = [0, 0, 0, 0] // ate 3 bananas from 4th pile
all the bananas are finished
so k=4 is a possible minimum eating speed
which is also the required answer
```

JavaScript

```
/**
* @param {number[]} piles
* @param {number} h
* @return {number}
*/
var minEatingSpeed = function(piles, h) {
const isAbleToEatAllBananas = k => {
let hoursTaken = 0;
piles.forEach(p => {
hoursTaken += Math.ceil(p/k);
});
return hoursTaken <= h;
};
let start = 1;
let end = Math.max(...piles);
while (start <= end) {
let mid = Math.floor((start + end) / 2);
if (isAbleToEatAllBananas(mid)) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return start;
};
```

**Time complexity: O(nlogM)**

The time complexity will be O(nlogM) where n is the number of piles and M is the largest pile.

**Space complexity: O(1)**

We are using constant space so space complexity will be O(1).

ADVERTISEMENT