#875 Koko Eating Bananas
frequently reported atAmazonAdobeMicrosoftBloombergMetaGoogle
the problem
In plain words
Koko eats k bananas per hour from one pile; if a pile has fewer than k she finishes it and waits for the next hour. Given piles and h hours, return the minimum integer k that lets her finish in time.
in piles = [3,6,7,11], h = 8
out 4
At 4/hour: 1 + 2 + 2 + 3 = 8 hours.
in piles = [30,11,23,4,20], h = 5
out 30
in piles = [30,11,23,4,20], h = 6
out 23
- 1 ≤ piles.length ≤ 10⁴
- piles.length ≤ h ≤ 10⁹
- 1 ≤ piles[i] ≤ 10⁹
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternBinary search on the answer
If speed k works, every speed above k works too. So "works?" over speeds 1..max(piles) reads F F F T T T — find the first T with binary search.
solutions
From brute force to optimal
Return the first speed whose total hours fit in h.
- For k = 1, 2, …: hours = Σ ⌈pile / k⌉.
- First k with hours ≤ h is the answer.
Up to M = max pile speeds, each checked in O(n). M can be 10⁹.
A running sum.
class Solution { public int minEatingSpeed(int[] piles, int h) { for (int k = 1; ; k++) { // the first speed that works is the answer long hours = 0; for (int p : piles) hours += (p + k - 1L) / k; if (hours <= h) return k; } }}Search speeds in [1, max pile] for the first one that finishes in h hours.
- lo = 1, hi = max(piles) (always works since h ≥ n).
- hours(mid) ≤ h → hi = mid (maybe slower works too).
- Else lo = mid + 1.
- Return lo.
≈ 30 guesses for M = 10⁹, each an O(n) pass.
A few counters.
class Solution { public int minEatingSpeed(int[] piles, int h) { int lo = 1, hi = 0; for (int p : piles) hi = Math.max(hi, p); // speed = biggest pile always works (h >= n) while (lo < hi) { int mid = lo + (hi - lo) / 2; if (hoursAt(piles, mid) <= h) hi = mid; // fast enough: answer is mid or slower else lo = mid + 1; // too slow: answer is faster than mid } return lo; // slowest speed that still works } private long hoursAt(int[] piles, int k) { long hours = 0; // long: can exceed 2^31 when k is small for (int p : piles) hours += (p + k - 1L) / k; // ceil(p / k) in integer math return hours; }}Dry run
in the room
How to say it in the interview
talk track
- Say: "The answer is a number in a range, and feasibility is monotonic — binary search on the answer."
- Write
hoursAt(k)first, then the search loop. - Call out the overflows: ceil with
long, and the hours sum inlong.
traps
Math.ceil(p / k)with ints does integer division first, so it rounds down — use(p + k − 1) / kinlong. (Math.ceilDivexists only from Java 18.)- Starting lo at 0 → division by zero.
- Summing hours in an
int: at k = 1 with 10⁴ piles of 10⁹ the total is 10¹³.
what they ask next
Follow-ups
Minimum Number of Days to Make m Bouquets (LC 1482)?
Same template: binary search the day; the check counts bouquets of k adjacent bloomed flowers in O(n).
before you submit
Edge cases to test
- h == piles.length: one pile per hour, so the answer is the biggest pile.
- Plenty of hours → speed 1.
- Huge piles at slow speeds: the hour total passes 2³¹ − 1 — [805306368, 805306368, 805306368] with h = 10⁹ needs a long sum.
practise next
Similar problems
- #1011Capacity To Ship Packages Within D DaysMediumin Binary Search
- #69Sqrt(x)Easyin Big-O
- #1631Path With Minimum EffortMediumin Shortest Paths