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 + (pile % speed != 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_element(piles.begin(), piles.end())
    while left < right:
        mid = left + (right - left) / 2
        hourSpend = 0
        for pile in piles:
            hourSpend += pile / mid + (pile % mid != 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).