875. Koko Eating Bananas

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

Table of Content

• Reference
• Problem Statement
• Approach
• Code
• Complexity

Reference: 875. Koko Eating Bananas

Problem statement

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.

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

Approach

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

Code

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;
};

Complexity

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).