Skip to content
DSAPrep

    ↑↓ to move · Enter to open · Esc to close

    MediumBinary Search

    Koko Eating Bananas

    Koko loves to eat bananas. There are n piles of bananas, the ith pile has piles[i] bananas. The guards have gone and will come back in h hours.

    Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour.

    Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.

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

    Example 1

    Input: piles = [3,6,7,11], h = 8

    Output: 4

    Example 2

    Input: piles = [30,11,23,4,20], h = 5

    Output: 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
    View original on LeetCode ↗

    Try Every Speed

    Time O(max(piles) * n)Space O(1)

    The brute-force way to find the minimum working speed is to try k = 1, 2, 3, ... in order and, for each one, compute how many hours it takes to clear every pile at that speed (ceil(pile / k) hours per pile). Stop at the first k that fits within h hours. Correct, but trying every candidate speed one at a time is wasteful.

    import math
    

    class Solution:
        def minEatingSpeed(self, piles: list[int], h: int) -> int:
            def hours_needed(k: int) -> int:
                return sum(math.ceil(p / k) for p in piles)
    

            k = 1
            while hours_needed(k) > h:
                k += 1
            return k

    Binary Search on the Answer

    OptimalTime O(n log(max(piles)))Space O(1)

    This is not a search over the input array — it is a search over the space of possible answers. The key structural fact: as the eating speed k increases, the number of hours needed is monotonically non-increasing. That monotonic relationship is exactly what binary search needs. So instead of scanning candidate speeds one by one, binary search directly on k, using hours_needed(k) <= h as the check: if the middle speed works, the answer is that speed or something smaller, so shrink the upper bound; otherwise it has to be bigger.

    import math
    

    class Solution:
        def minEatingSpeed(self, piles: list[int], h: int) -> int:
            def hours_needed(k: int) -> int:
                return sum(math.ceil(p / k) for p in piles)
    

            lo, hi = 1, max(piles)
            while lo < hi:
                mid = (lo + hi) // 2
                if hours_needed(mid) <= h:
                    hi = mid
                else:
                    lo = mid + 1
            return lo

    This trace shows both sides of each test at once: which candidate speed sits at the middle of the current window, and the pile-by-pile hours that speed costs (each pile costs ceil(pile / k)). Watch the window collapse from whichever half cannot contain the answer.

    Candidate speeds k = 1 through 11

    1234567891011

    Hours per pile at k = —

    3↓—
    6↓—
    7↓—
    11↓—
    Total—hourslimit 8
    1 / 6
    currentdiscardedresultcomparing

    The candidates are speeds 1 through 11, not the bananas in a pile. lo = 1 and hi = 11, and the answer is somewhere inside that window.

    Why it’s correct: hours_needed(k) is a non-increasing function of k, so the set of speeds that satisfy hours_needed(k) <= h is a contiguous suffix of [1, max(piles)]. Binary search finds the left boundary of that suffix, which is the minimum valid speed. Complexity: each hours_needed check costs O(n), and the search space [1, max(piles)] halves every step, giving O(log(max(piles))) iterations, for O(n log(max(piles))) time, O(1) space.

    More Binary Search practice