0875.Koko Eating Bananas

Link: 875. Koko Eating Bananas - Medium
Track: NeetCode150 Amazon

Question

Restate

• Given an array piles, where piles[i] is the number of bananas in the ith pile
• Koko can decide an integer eating speed k bananas per hour
• In one hour, she chooses one pile and eats up to k bananas from that pile
• If the pile has fewer than k bananas, she eats the whole pile and stops for that hour
• Return the minimum integer k such that Koko can finish all piles within h hours

Edge Case

• len(piles) == 1
• h == len(piles) → Koko must finish exactly one pile per hour, so answer is max(piles)

---

Method	Approach	Time Complexity	Space Complexity
Method 1 ⭐	Binary Search	$O(n\cdot log(max(piles)))$	$O(1)$

Method 1 - Binary Search

Approach

• The minimum possible speed is 1
• The maximum possible speed is max(piles)
• For each candidate speed mid:
  • compute how many total hours Koko needs
  • hours for one pile = ceil(pile / mid)
• If total hours <= h, this speed works
  • try smaller speed
• Otherwise, this speed is too slow
  • try larger speed

Complexity

• Time Complexity: $O(n\cdot log(max(piles)))$
• Space Complexity: $O(1)$

Code

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        if len(piles) > h:
            return 0
        
        left, right = 1, max(piles)
        ans = 0
        
        while left <= right: # [1, 30]
            spd = (left + right) // 2 # spd = 15
            cur_hr = 0
            for pile in piles:
                cur_hr += (pile + spd - 1) // spd # 2, 1,2,1,2
            
            # print(cur_hr, spd)
            if cur_hr <= h: # 6 <= 8
                ans = spd
                right = spd - 1 # slow the speed
            else: # cur_hr > h
                left = spd + 1
        
        return ans  

---

Mistake

• Use floor division pile // spd instead of ceiling division
  • ceiling math (pile + spd - 1) // spd