← DSA Atlas
Dedicated problem page · #875

Koko Eating Bananas

MediumBinary SearchBinary search on the answerBinary search over a monotonic feasibility predicate
Solve on LeetCode ↗
875
MediumBinary SearchBinary search over a monotonic feasibility predicateBinary search on the answer

Koko Eating Bananas

Koko has n piles of bananas, where piles[i] is the count in the i-th pile, and the guards return in h hours. Each hour Koko picks one pile and eats up to k bananas from it; if the pile has fewer than k she finishes it and stops for that hour. Return the minimum integer eating speed k so she can finish all bananas within h hours.

Open official problem prompt ↗
In plain English

Find the slowest constant eating speed that still clears every pile within the allotted hours.

Picture it like this

Like tuning a shower knob to the lowest flow that still fills the tub before your alarm rings: turn it up when you are behind, ease it down when you have spare time, converging on the exact threshold.

Example
Input
piles = [3, 6, 7, 11], h = 8
Output
4
Why
At speed 4 the hours are ceil(3/4)+ceil(6/4)+ceil(7/4)+ceil(11/4) = 1+2+2+3 = 8, which fits in h; speed 3 would need 9 hours.
Constraints
1 <= piles.length <= 10^4piles.length <= h <= 10^91 <= piles[i] <= 10^9
Pattern lesson

See the pattern, then code

Binary search on the answer
Recognition clue

You are asked for the minimum rate/capacity such that a task fits a limit, and 'faster works, slower fails' is monotonic, which is the textbook signal for binary search on the answer.

↗
Binary Search

Sorted data or a monotonic true/false condition over a possible answer.. If speed k lets Koko finish in time, any speed greater than k also does; this monotonicity lets you binary-search the smallest feasible k instead of trying every value.

New words, made simpleKnow these before the algorithm
Binary search on the answer
Searching over the space of possible answers, using a yes/no feasibility test at each candidate, instead of over array indices.
Monotonic predicate
A feasibility test that, once true, stays true for all larger candidates.
Ceiling division
(p + k - 1) // k computes hours for a pile without floating point.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Try every speed from 1 upward

With m up to 10^9 this is far too slow.

Increment k until the total hours fit.

Time O(n * m)Space O(1)
Best choiceBinary search on speed

Exploits monotonicity for a fast, exact answer.

Binary-search k in [1, max(piles)] using the hours predicate.

Time O(n log m)Space O(1)
The rule we keep true

Invariant

The smallest feasible speed always lies within [lo, hi].

Why this is correct

Reasoning

hours(k) is non-increasing in k: a larger speed never takes more hours. So feasibility flips from false to true exactly once as k grows. Binary search keeps the boundary inside [lo, hi] and converges on the first feasible k.

The algorithm in three movesSay these aloud before coding
1Set the search range to [1, max(piles)] since eating faster than the biggest pile never helps

lo=1, hi=11, mid=6 -> hours=1+1+2+2=6 <= 8, hi=6

2For a candidate speed mid, compute total hours as the sum of ceil(pile / mid)

lo=1, hi=6, mid=3 -> hours=1+2+3+4=10 > 8, lo=4

3If hours <= h the speed is feasible, so shrink hi to mid; else raise lo to mid + 1

lo=4, hi=6, mid=5 -> hours=1+2+2+3=8 <= 8, hi=5; mid=4 -> hours=8 <= 8, hi=4 -> return 4

4Return lo, the smallest feasible speed

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
30
61
72
113
1 · Readlo=1, hi=11, mid=6
2 · AskDo 6 bananas/hr finish in 8 hours?
3 · Update statehours = 6
4 · Resultfeasible, hi = 6
Key takeaway

The feasibility boundary sits at speed 4; slower is too slow, faster is wasteful.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3Bound the search

    Speed 1 is the slowest sensible rate and max(piles) always finishes in n hours <= h, so the answer lives in this range.

  2. 2
    Lines 6Feasibility test

    Ceiling division sums the exact hours needed at speed mid without floats.

  3. 3
    Lines 7-10Shrink toward the boundary

    Feasible speeds pull hi down (keeping mid), infeasible speeds push lo up past mid.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • A single pile
  • h equal to the number of piles, forcing speed = max(piles)
  • Very large piles up to 10^9 (no overflow in Python but tests the bound)
  • All piles equal
!

Common beginner mistakes

  • Starting lo at 0, which causes a division by zero
  • Using floating-point division and rounding, which can misjudge hours
  • Setting hi too low (e.g. sum(piles)) and missing that each hour only touches one pile
Check your understanding

Why is max(piles) a safe upper bound for the speed?

More in Binary Search

#33Search in Rotated Sorted ArrayBinary search on a rotated array#153Find Minimum in Rotated Sorted ArrayBinary search for the rotation point#4Median of Two Sorted ArraysBinary search on the partition#34Find First and Last Position of ElementLower-bound binary search on both ends#35Search Insert PositionLower-bound binary search#74Search a 2D MatrixBinary search on a flattened grid