Domain 2MediumMEDIUM

Koko Eating Bananas

LeetCode problem 875: Koko Eating Bananas (medium).

Domain: medium•Updated: 2026-09-03
#Binary Search

Problem Breakdown

We are given an array of banana piles where each pile has a specific number of bananas (piles[i]). Koko needs to eat all these bananas within h hours before the guards return. She chooses a constant eating speed k. In one hour, she eats up to k bananas from one chosen pile. If a pile is smaller than k, she finishes it and stops for that hour (wasting remaining time).

Inputs:

  • piles: List of integers representing banana counts per pile (1≤piles[i]≤1091 \le piles[i] \le 10^9).
  • h: Total hours available (N≤h≤109N \le h \le 10^9, where N=len(piles)N = len(piles)).

Output:

  • Minimum integer speed k to finish all bananas within h.

Implicit Constraints & Edge Cases:

  • Monotonicity: If a specific speed k works, any speed greater than k will also work (finish time decreases or stays same as speed increases). This is the critical property for Binary Search.
  • Search Space Lower Bound: Speed must be at least 1 (low = 1).
  • Search Space Upper Bound: We never need to eat faster than the largest pile in a single hour, because that guarantees every pile finishes within exactly one hour (total time NN). Since h >= N, this is always feasible. Thus, high = max(piles).
  • Feasibility Check: For any speed k, total hours required is ∑⌈piles[i]/k⌉\sum \lceil piles[i] / k \rceil. We must ensure this sum does not exceed h.

Intuition

A naive brute force approach would be to iterate through every possible integer value of k starting from 1 up to the maximum pile size. For each k, we calculate if it’s feasible within h hours. However, since piles can have values up to 10910^9, iterating linearly is too slow (O(max⁡(piles)⋅N)O(\max(piles) \cdot N)).

The key insight lies in recognizing that feasibility is monotonic with respect to speed:

  • If Koko eats at speed k, she finishes within time.
  • Increasing her speed will only reduce or keep the same total hours needed; it never increases them.
  • Decreasing her speed below a working threshold might cause her to exceed h.

This allows us to use Binary Search on the Answer (the value of k). We search for the smallest valid k in the range [1,max⁡(piles)][1, \max(piles)]. This reduces our complexity significantly.

Approach

  1. Initialize binary search bounds: left = 1, right = max(piles).
  2. While left <= right:
    • Calculate mid = (left + right) // 2 as the candidate speed.
    • Check if this speed is feasible within h hours using a helper calculation or inline logic: sum of (pile + mid - 1) // mid for all piles. This formula computes ⌈pile/k⌉\lceil pile / k \rceil efficiently without floating point errors.
  3. If the total time required with mid speed is less than or equal to h:
    • Record mid as a potential answer (ans = mid).
    • Try finding a slower valid speed by moving right bound: right = mid - 1.
  4. If the total time exceeds h:
    • The current speed is too slow; we need to eat faster. Move left bound up: left = mid + 1.
  5. Return the recorded answer (ans).

Complexity Analysis

  • Time Complexity: O(N⋅log⁡(max⁡(piles)))O(N \cdot \log(\max(piles))). We perform a binary search over the range of possible speeds (up to ≈30\approx 30 iterations for max value 10910^9). Inside each iteration, we iterate through all piles (NN) to calculate total hours. With N=104N=10^4, this is roughly 3⋅1053 \cdot 10^5 operations, well within time limits.
  • Space Complexity: O(1)O(1) auxiliary space (excluding input storage). We only use a few integer variables for the search bounds and counters.

Solution

import math

def minEatingSpeed(piles: list[int], h: int) -> int:
    # Binary Search on Answer Space
    
    left, right = 1, max(piles)
    
    while left <= right:
        k = (left + right) // 2
        
        # Calculate total hours needed for speed k
        # Using integer arithmetic to avoid float precision issues: ceil(a/b) -> (a + b - 1) // b
        time_needed = sum((pile + k - 1) // k for pile in piles)
        
        if time_needed <= h:
            ans = k       # Found a valid speed, try smaller one to minimize k
            right = k - 1 
        else:
            left = k + 1   # Not fast enough
            
    return left

# Example usage matching LeetCode signature logic (returning the found min)

Edge Cases Handled

  • Single Pile: The binary search correctly handles cases where len(piles) is 1. If there’s only one pile, Koko just needs to eat it within h hours; speed will be ⌈piles[0]/h⌉\lceil piles[0] / h \rceil.
  • Large Values (piles[i]piles[i] up to 10910^9): Python handles large integers automatically without overflow issues. The ceiling division formula (pile + k - 1) // k ensures precision is maintained using integer arithmetic rather than floating point math.ceil.
  • Minimum Time Constraint: Since the problem guarantees a solution exists (and specifically that h≥len(piles)h \ge len(piles)), we don’t need to handle impossible cases where even infinite speed cannot finish in time. The upper bound of binary search ensures we find the minimum valid integer within feasible bounds.