Koko Eating Bananas

Leetcode Daily Challenge (8th March, 2023)

8 March, 2023

Contributors

Lakshit Chiranjiv Sagar

@lakshit-cs

Problem Statement:-

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.

Link: https://leetcode.com/problems/koko-eating-bananas/

Problem Explanation with examples:-

Example 1

Input: piles = [3,6,7,11], h = 8
Output: 4
Explanation: 4 is the minimum K such that we can eat all the bananas within 8 hours.
- in 1st hour, koko eats the 1st pile of 3 bananas
- in 2nd hour, koko eats the 4 bananas from the 2nd pile (2nd pile of 6 bananas)
- in 3rd hour, koko eats the remaining 2 bananas from the 2nd pile 
- in 4th hour, koko eats the 4 bananas from the 3rd pile (3rd pile of 7 bananas)
- in 5th hour, koko eats the remaining 3 bananas from the 3rd pile
- in 6th hour, koko eats the 4 bananas from the 4th pile (4th pile of 11 bananas)
- in 7th hour, koko eats the next 4 bananas from the 4th pile
- in 8th hour, koko eats the remaining 3 bananas from the 4th pile

Example 2

Input: piles = [30,11,23,4,20], h = 5
Output: 30
Explanation: 30 is the minimum K such that we can eat all the bananas within 5 hours.
- in 1st hour, koko eats 30 bananas from the 1st pile
- in 2nd hour, koko eats 11 bananas from the 2nd pile
- in 3rd hour, koko eats 23 bananas from the 3rd pile
- in 4th hour, koko eats 4 bananas from the 4th pile
- in 5th hour, koko eats 20 bananas from the 5th pile

Example 3

Input: piles = [30,11,23,4,20], h = 6
Output: 23
Explanation: 23 is the minimum K such that we can eat all the bananas within 6 hours.
- in 1st hour, koko eats 23 bananas from the 1st pile
- in 2nd hour, koko eats remaining 7 bananas from the 1st pile
- in 3rd hour, koko eats 11 bananas from the 2nd pile
- in 4th hour, koko eats 23 bananas from the 3rd pile
- in 5th hour, koko eats 4 bananas from the 4th pile
- in 6th hour, koko eats 20 bananas from the 5th pile

Constraints

1 <= piles.length <= 10^4
piles.length <= h <= 10^9
1 <= piles[i] <= 109

Intuition:-

The lowest possible answer can be 1 when Koko eats 1 banana per hour
The highest possible answer can be the max number of bananas from the piles
Now thinking of bounds, what is the best way to find the answer?
We can use binary search to find the answer
In each iteration, we find the midpoint between the bounds
We then check how many hours it would take to eat all the bananas at that speed
Accordinly we update the bounds i.e. increase or decrease the speed
We continue this until the bounds converge to the answer
The answer is the lower bound

Solution:-

First, we can see that the answer is in the range of [1, max(piles)]
Initialize l = 1, r = max(piles)
Then run a while loop, while l < r
In the while loop, calculate mid = (l+r)//2
Then take a variable hrs = 0 to count how many hours it would take Koko to eat all bananas at m speed
For each pile in the pile array, we can calculate the number of hours it takes to eat that pile at m bananas/hour speed by taking the ceiling value of pile/m and add it to hrs
Finally, compare hrs with h, if hrs > h, we can set l = m+1, otherwise, we can set r = m
After the while loop, we can return l

Code:-

JAVA Solution

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int l = 1;
        int r = Arrays.stream(piles).max().getAsInt();
        while (l < r) {
            int m = (l + r) / 2;
            int hrs = 0; // hrs needed to eat at speed m/hr
            for (int i : piles) {
                hrs += (int) Math.ceil((double) i / m);
            }
            if (hrs > h) {
                l = m + 1;
            } else {
                r = m;
            }
        }
        return l;
    }
}

Python Solution

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        l = 1
        r = max(piles)
        while l < r:
            m = (l+r)//2
            hrs = 0 #hrs needed to eat at speed m/hr
            for i in piles:
                hrs += math.ceil(i/m)
            if hrs > h:
                l = m+1
            else:
                r = m

        return l

Complexity Analysis:-

TIME:-

Time complexity is O(NlogN) as we are doing a binary search on the range of possible speeds, and for each speed, we are doing a linear search to find the number of hours needed to eat all the bananas.

SPACE:-

Space complexity is O(1), as we are not using any extra space.