875. Koko Eating Bananas — LeetCode(Python)

I got you!

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.

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 <= 104
• piles.length <= h <= 109
• 1 <= piles[i] <= 109

Solution:

l, r = 1, max(piles)
res = r
        
while l <= r:
    k = (l + r) // 2
    hours = 0
    for p in piles:
        hours += math.ceil(p / k)
                
    if hours <= h:
        res = min(res, k)
        r = k - 1
    else:
        l = k + 1
                
return res

Explanation —

We know that the minimum speed Koko can eat at is 1 banana per hour. But what is the maximum valid speed?

Since Koko likes eating slowly, there is no point eating faster then the maximum pile length per hour.

If Koko eats at max(piles) speed, she will take time = len(piles) to eat all bananas. And we are given,

• piles.length <= h <= 109

Thus, this speed is always valid. It is the “minimum fastest” speed.

Now, we try to find an optimum speed between 1 and max(piles).

A binary search solution automatically comes to mind.

We perform binary search between 1 and max(piles) and at each iteration, disregard half of this range until eventually we run out of options.

• We find the mid of a given range.
• Then, we calculate the number of hours it would take Koko to eat all bananas at this speed.
• If this speed is valid, we try to search for a slower speed, since Koko likes it slow;)
• If this speed is invalid, Koko needs to increase her speed, so we search only in the larger numbers in the range.

Time and Space Complexity —

Since, this is a binary search procedure, our time and space complexities are the same.

Thus, if p is the length of the array piles,

Time Complexity: O(log(max(piles)).p)

Space Complexity: O(1)

Feel free to ask any related questions in the comment section or the links provided down below.

I don’t have friends:

Let’s be friends!

Connect with me on:

LinkedIn

GitHub

Instagram (I know. Very professional)

Jai Shri Ram 🙏