LeetCode 875 - Koko Eating Bananas

2026-07-06

medium　array　binary search

If you're not familiar with binary search, check out LeetCode 704 - Binary Search first.

You are given an integer array piles where piles[i] is the number of bananas in the i-th pile. You are also given an integer h, the number of hours available to eat all the bananas.

You may choose a bananas-per-hour eating rate of k. Each hour, you pick one pile and eat k bananas from it. If the pile has fewer than k bananas, you finish it but cannot start another pile in the same hour.

Return the minimum integer k such that you can eat all the bananas within h hours.

Example 1:

Input: piles = [1,4,3,2], h = 9

Output: 2

Explanation: At speed 2, you need 6 hours. At speed 1, you need 10 hours (exceeds h=9). So the minimum speed is 2.

Example 2:

Input: piles = [25,10,23,4], h = 4

Output: 25

Constraints:

• 1 <= piles.length <= 1,000
• piles.length <= h <= 1,000,000
• 1 <= piles[i] <= 1,000,000,000

Solution 1:

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        # Approach: Brute Force — Linear Scan from Speed 1
        # 1. Try every speed starting from 1.
        # 2. For each speed, compute the total hours needed:
        #    ceil(pile / speed) per pile, summed up.
        #    Using integer arithmetic: ceil(a / b) == (a + b - 1) // b.
        # 3. Return the first speed where total hours <= h.
        # Time Complexity: O(M * N) — M = max(piles) speeds tried, N = number of piles.
        # Space Complexity: O(1).
        # Note: This TLEs on LeetCode when piles[i] is up to 1,000,000,000.
        speed = 1
        while True:
            hours = 0
            for p in piles:
                hours += (p + speed - 1) // speed
            if hours <= h:
                return speed
            speed += 1

Solution 2:

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        # Approach: Binary Search on the Answer Space
        # The valid speed range is [1, max(piles)]:
        #   - Speed 1 is the slowest possible (always valid if h is large enough).
        #   - Speed max(piles) finishes the largest pile in one hour (always fast enough).
        # The hours-needed function is monotonically decreasing as speed increases,
        # so we can binary search for the minimum speed where hours <= h.
        # 1. Compute total hours at the midpoint speed.
        # 2. If hours <= h, this speed works — try slower (move right pointer left).
        # 3. If hours > h, too slow — move left pointer right.
        # 4. When pointers cross, l_idx is the minimum valid speed.
        # Time Complexity: O(N log M) — log M binary search steps, each scanning N piles.
        # Space Complexity: O(1).
        l_idx, r_idx = 1, max(piles)
        while l_idx <= r_idx:
            speed = (l_idx + r_idx) // 2
            hours = 0
            for p in piles:
                hours += (p + speed - 1) // speed
            if hours <= h:
                r_idx = speed - 1
            else:
                l_idx = speed + 1
        return l_idx

Solution 3:

import math

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        # Approach: Binary Search with Tightened Bounds
        # Two optimizations over Solution 2:
        # 1. If len(piles) == h, there is exactly one hour per pile — must finish each pile
        #    in one hour, so the answer is max(piles) directly.
        # 2. The lower bound can be raised from 1 to ceil(sum(piles) / h):
        #    we must eat at least that many bananas per hour on average to finish in time.
        #    This shrinks the binary search range and reduces iterations.
        # Time Complexity: O(N log M) — same asymptotic, but smaller constant due to tighter bounds.
        # Space Complexity: O(1).
        if len(piles) == h:
            return max(piles)

        l_idx = math.ceil(sum(piles) / h)
        r_idx = max(piles)
        while l_idx <= r_idx:
            speed = (l_idx + r_idx) // 2
            hours = 0
            for p in piles:
                hours += (p + speed - 1) // speed
            if hours <= h:
                r_idx = speed - 1
            else:
                l_idx = speed + 1
        return l_idx

Conclusion

Today we solved Koko Eating Bananas — a classic example of binary searching on the answer space rather than on an index.

The brute-force approach tries every speed from 1 upward. It works in theory but times out because piles[i] can be up to one billion, making the search space enormous.

The key insight: the total hours needed is a monotonically decreasing function of speed. That means we don't need to scan every speed — we can binary search. The range is [1, max(piles)], and we look for the leftmost speed where total_hours <= h. Each midpoint check costs O(N) to scan all piles, and binary search does O(log M) steps, giving O(N log M) overall.

Solution 3 tightens the lower bound from 1 to ceil(sum(piles) / h) — the minimum average speed required just to cover the total banana count. This cuts the search range and reduces the number of iterations without changing the asymptotic complexity.

The ceiling division trick (a + b - 1) // b is worth remembering — it computes ceil(a / b) using only integer arithmetic, which avoids floating-point issues entirely.