AlgoViz
HomeBinary Search

Apple Harvest (Koko Eating Bananas)

Medium

Binary search the eating speed

Problem

Koko eats bananas from piles at a chosen speed of s bananas/hour, finishing one pile per hour at most. Given the piles and h hours, return the smallest speed s that lets her finish all bananas within h hours.

In simple words

Binary-search the eating speed: guess a rate, check if she finishes in time, and narrow the range.

The idea

Eating faster never takes more hours, so the predicate 'finishes within h hours at speed s' is monotone. Binary search s from 1 to the largest pile, computing the hours as a sum of ceilings.

The trick

  • Hours for a pile = ceil(pile / s), which is (pile + s - 1) / s in integers.
  • Upper bound is max(piles) — faster than that changes nothing.
  • O(n log max) instead of trying every speed.
1
2
3
4
5
6
7
8
9
10
11
0
1
2
3
4
5
6
7
8
9
10
candidates11

Step 1 of 6. Brute force: try every eating speed from 1 up until Koko finishes within 8 hours. Values: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11. candidates 11.

1/6
Brute force
timeO(max·n)spaceO(1)

Try every speed.

1let best = -1;2for (let k = 1; k <= maxPile && best < 0; k++)3  if (hoursNeeded(k) <= h) best = k;4return best;

Input

array
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

Memory

try
—
candidates
11
speed
—

Output

speed
—
answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
piles = [3, 6, 7, 11], h = 8
Output:
4
Explanation:
Eating 4 bananas/hour finishes in time.

Example 2

Input:
piles = [30, 11, 23, 4, 20], h = 5
Output:
30
Explanation:
She must eat 30/hour to finish in 5 hours.

Example 3

Input:
piles = [30, 11, 23, 4, 20], h = 6
Output:
23
Explanation:
One extra hour lets her slow to 23/hour.

Constraints

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

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.