DSAPrep
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

Tracing piles = [3,6,7,11], h = 8 — the array below represents the candidate speeds 1 through 11, not the piles:

lo
1
0
2
1
3
2
4
3
5
4
mid
6
5
7
6
8
7
9
8
10
9
hi
11
10
lo = 1mid = 6hi = 11hours = 6
1 / 5
comparingresultdiscarded

At speed 6, Koko needs 6 hours, which fits in 8. Speed 6 works, so the answer is at most 6 -- discard every speed above it and set hi = mid.

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.