Skip to main content

875. Koko Eating Bananas

medium

Find the minimum eating speed Koko needs to finish all bananas within h hours. The cleanest 'binary-search on the answer' problem — pattern recognition unlocks dozens of others.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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.

Constraints

  • 1 <= piles.length <= 10^4
  • piles.length <= h <= 10^9
  • 1 <= piles[i] <= 10^9

Examples

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Brute-force every speed from 1 to max(piles) and check feasibility — O(max * n). Too slow.

Hint 2

Notice monotonicity: if speed k works, every k' > k works too. That's the cue to binary-search on the answer.

Hint 3

Search space: lo = 1, hi = max(piles). Predicate: at speed k, sum of ceil(piles[i] / k) over all piles <= h.

Hint 4

Standard 'find leftmost true' binary search — narrow toward the smallest k where the predicate holds.

Solution approach

Reveal approach

Binary search on the answer. Set lo = 1 and hi = max(piles). Define canEatAt(k): for each pile compute ceil(piles[i] / k) (use (piles[i] + k - 1) / k or math.ceil) and sum; return sum <= h. The predicate is monotonic — if k works, every larger k does too. Standard leftmost-true binary search: while lo < hi, mid = lo + (hi - lo) / 2; if canEatAt(mid), hi = mid; else lo = mid + 1. Return lo. Each predicate call is O(n) and we do O(log(max)) iterations, so O(n log(max(piles))) time and O(1) space.

Complexity

Time
O(n log m) where m = max(piles)
Space
O(1)

Related patterns

  • binary-search
  • binary-search-on-answer

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Meta
  • Uber

Practice these live with InterviewChamp.AI

Drill Koko Eating Bananas and Binary Search problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →