[Medium] 875. Koko Eating Bananas

Problem Statement

Koko has n piles of bananas; the i-th pile has piles[i] bananas. The guards return in h hours. Koko can choose an integer eating speed k (bananas per hour). Each hour she picks one pile and eats k bananas from it; if the pile has fewer than k, she eats all of them and does not eat from another pile that hour. Return the minimum integer k such that she can finish all bananas within h hours.

Examples

Example 1:

Input: piles = [3,6,7,11], h = 8
Output: 4
Explanation: At speed 4: (3/4 + 6/4 + 7/4 + 11/4) = 1+2+2+3 = 8 hours.

Example 2:

Input: piles = [30,11,23,4,20], h = 5
Output: 30
Explanation: She must finish in 5 hours, so speed must be at least max(piles) = 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

Solution Approach

  • Feasibility: For speed k, hours needed = sum over piles of ceil(pile / k) = pile / k if divisible, else pile / k + 1. In code: pile / k + (pile % k != 0).
  • Minimize k: We want the smallest k such that total hours ≤ h. Speed is in range [1, max(piles)].
  • Brute force: Try k = 1, 2, 3, ... until feasible. Too slow when max(piles) is large.
  • Optimized: Binary search on k in [1, max(piles)]. For each mid, compute hours; if hours <= h then mid is feasible, so search left (right = mid), else search right (left = mid + 1). Return the smallest feasible k (the leftmost that works).

Solution 1: Linear Search (Brute Force)

Try speed 1, 2, 3, … until total hours ≤ h.

class Solution:
    def minEatingSpeed(self, piles, h):
        speed = 1
        
        while True:
            hourSpend = 0
            
            for pile in piles:
                hourSpend += pile // speed + (1 if pile % speed != 0 else 0)
                
                if hourSpend > h:
                    break
            
            if hourSpend <= h:
                return speed
            else:
                speed += 1
  • Time: O(n × max(piles)) in the worst case — too slow for large piles.
  • Space: O(1).

Solution 2: Binary Search on Answer

Binary search on k in [1, max(piles)]; for each mid, compute total hours and narrow the range.

class Solution:
    def minEatingSpeed(self, piles, h):
        left = 1
        right = max(piles)
        
        while left < right:
            mid = left + (right - left) // 2
            
            hourSpend = 0
            for pile in piles:
                hourSpend += pile // mid + (1 if pile % mid != 0 else 0)
            
            if hourSpend <= h:
                right = mid
            else:
                left = mid + 1
        
        return right
  • Invariant: right is always feasible; we look for the smallest feasible k, which is right when left == right.
  • Time: O(n log(max(piles))). Space: O(1).

Key Insights

  1. Binary search on the answer: When the answer is in a range and feasibility is easy to check, binary search on that range.
  2. Ceiling division: pile / k + (pile % k != 0) or (pile + k - 1) / k gives hours per pile.
  3. Range: Minimum speed is 1; maximum needed is max(piles) (one hour per pile).