0875. Koko Eating Bananas

Medium | Binary Search | 372 ms (97.73%), 15.5 MB (87.10%)

❓ Problem Statement

Source: LeetCode - Koko Eating Bananas GitHub: Solution / Performance

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.

✍🏻 Constraints & Example

Constraints:

• 1 <= piles.length <= 10^4

• piles.length <= h <= 10^9

• 1 <= piles[i] <= 10^9

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

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

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

💡 Ideas

Binary Search Problem Find a minimum speed that Koko can eat all the bananas within h hours.

Boundary / Search Space

Left (Minimum) = 1 Right (Maximum) = MAX pile (the number of bananas)

Condition

While Loop = Left < Right

Return Value

Left

🤖 Python3

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        
        # ==================================================
        #  Binary Search                                   =
        # ==================================================
        # time  : O(nlog(m)), m is the search space
        # space : O(1)
        
        l, r = 1, max(piles)
        while l < r:
            speed = (l + r) // 2
            
            if sum(ceil(pile / speed) for pile in piles) <= h: r = speed
            else: l = speed + 1
        
        return l

🤖 Java

class Solution {
    /**
     * @time  : O(nlog(m)), m is the search space
     * @space : O(1)
     */
    
    public int minEatingSpeed(int[] piles, int h) {
        int l = 1, r = 1000000000;
        while (l < r) {
            int m = (l + r) / 2, total = 0;
            for (int p : piles) total += (p - 1) / m + 1;
            
            if (total <= h) r = m;
            else l = m + 1;
        }
        return l;
    }
}