DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Koko Eating Bananas

mediumBinary search

Problem statement

There are several piles of bananas, given as an array piles, and a deadline of h hours (h is at least the number of piles). An eater picks one fixed integer speed k bananas per hour. Each hour, they choose one pile and eat up to k bananas from it. If the pile has fewer than k left, they finish it and do nothing else for the rest of that hour.

Return the smallest speed k that lets them finish every pile within h hours.

Put another way: a pile of size p takes ceil(p / k) hours, and the sum of those hours must be at most h.

Examples

Example 1

Input: piles = [4, 9, 13], h = 6

Output: 5

Explanation: At speed 5 the piles take 1 + 2 + 3 = 6 hours. At speed 4 they take 1 + 3 + 4 = 8 hours, which is too slow.

Example 2

Input: piles = [12, 7], h = 5

Output: 4

Explanation: Speed 4 needs 3 + 2 = 5 hours. Speed 3 needs 4 + 3 = 7.

Hints

Approach

Binary-search the answer instead of the array. Define fast_enough(k) as "total hours at speed k is at most h". It is false for small k and true from some point on, and we want the first true.

  1. Set lo = 1 and hi = max(piles). hi is always fast enough.
  2. While lo < hi:
    • mid = lo + (hi - lo) // 2;
    • if fast_enough(mid), the answer is mid or smaller: hi = mid;
    • otherwise it is larger: lo = mid + 1.
  3. Return lo.

Each check costs O(n) and there are O(log M) checks.

ComplexityTime O(n log M)Space O(1)
Python
class Solution:
def minEatingSpeed(self, piles: list[int], h: int) -> int:
def fast_enough(k: int) -> bool:
return sum((p + k - 1) // k for p in piles) <= h
lo, hi = 1, max(piles)
while lo < hi:
mid = lo + (hi - lo) // 2
if fast_enough(mid):
hi = mid
else:
lo = mid + 1
return lo

Follow-up questions

  • Each pile now has a different eating rate multiplier. Does binary search on the answer still work?
  • Instead of one eater, there are w eaters working in parallel on separate piles. What changes in the check?

Frequently asked questions

It is capacity planning in disguise. Replace piles with queue backlogs and the speed with messages per worker per minute: what is the minimum throughput to drain every queue before a maintenance window closes? "Binary-search the smallest setting that passes a check" is a pattern you will reuse often.

Use (p + k - 1) // k. Floating-point division with math.ceil(p / k) works for small values but can round wrongly for very large integers, and it is slower.

With speed 1 and many large piles, the total hours can pass the int limit of about 2.1 billion and wrap to a negative number, which would make a too-slow speed look fast enough.