Start learning free

LESSON 335 OF 540 · BINARY SEARCH

Koko Eating Bananas in Go: O(n log m) Binary Search on the Answer

Practice O(n log m) Read the full explanation

Koko loves to eat bananas. There are n piles of bananas, and pile i has piles[i] bananas. The guards have gone and will come back in h hours.

Koko chooses an eating speed of k bananas per hour. Each hour, she picks one pile and eats k bananas from it. If the pile has fewer than k bananas, she eats all of them and eats nothing more during that hour. So a pile of p bananas takes her p / k hours, rounded up.

Given an array of integers piles and an integer h, return the smallest integer speed k that lets Koko eat all the bananas within h hours.

Example 1:

Input: piles = [3,6,7,11], h = 8
Output: 4
Explanation: At speed 4 the piles take 1 + 2 + 2 + 3 = 8 hours, just in time. At speed 3 they would take 1 + 2 + 3 + 4 = 10 hours, too many.

Example 2:

Input: piles = [30,11,23,4,20], h = 5
Output: 30
Explanation: There are as many hours as piles, so every pile must be eaten in one hour, and the biggest pile has 30 bananas.

Example 3:

Input: piles = [30,11,23,4,20], h = 6
Output: 23
Explanation: At speed 23 the piles take 2 + 1 + 1 + 1 + 1 = 6 hours. At speed 22 the pile of 23 takes 2 hours too, so they take 2 + 1 + 2 + 1 + 1 = 7 hours.

Constraints:

1 <= n <= 10⁴, where n is the number of piles
n <= h <= 10⁹
1 <= piles[i] <= 10⁹

Note:

Your algorithm should run in O(n log m) time, where m is the biggest pile, and use O(1) extra space.

At a slow speed the hours add up fast: 10⁴ piles of 10⁹ bananas take 10¹³ hours at speed 1, far more than a 32-bit integer can hold.

STEP 1 OF 15

Guided

Ctrl + Enter to check

GO · BINARY SEARCH

Koko Eating Bananas in Go, explained

Problem overview

Koko has n piles of bananas, and piles[i] is the size of pile i. The guards return in h hours. Koko picks a speed of k bananas per hour. Each hour she works on a single pile: she eats k bananas from it, or the whole pile if it has fewer than k, and then the hour is over. A pile of p bananas therefore takes p / k hours, rounded up.

The function minEatingSpeed(piles []int, h int) int returns the smallest integer speed that finishes every pile within h hours.

For piles = [3, 6, 7, 11] and h = 8 the answer is 4. At speed 4 the piles take 1 + 2 + 2 + 3 = 8 hours, just in time. At speed 3 they take 1 + 2 + 3 + 4 = 10 hours, which is too many.

The lesson asks for O(n log m) time, where m is the biggest pile, and O(1) extra space.

Approach: binary search on the answer

The slow way is to try speeds 1, 2, 3, and so on, computing the total hours for each until one fits. With piles up to 10^9 that can mean a billion attempts.

The useful observation is about the shape of the problem. If Koko finishes in time at speed k, she also finishes at any faster speed, because no pile takes longer. If she doesn't finish at speed k, no slower speed works either. So going through the speeds from 1 upward, the answer to "is this fast enough?" is no, no, no, then yes, yes, yes: it flips exactly once. Binary search finds the flip point, even though there is no array of speeds to search. This is binary search on the answer.

The search range is easy to bound. Speed 1 is the slowest sensible speed. The biggest pile is a speed that always works, since every pile then takes one hour and the statement guarantees n <= h. No answer is ever bigger, so the range is 1 to the biggest pile.

Each probe needs the total hours at a speed k. A helper, hours, adds up the hours of every pile, which is O(n). The search makes about log2(m) probes, hence O(n log m).

On [3, 6, 7, 11] with h = 8, the probes are:

l 1 r 11 k 6 hours 6
l 1 r 5 k 3 hours 10
l 4 r 5 k 4 hours 8

Speed 6 is fast enough, so the search looks lower, at 1 to 5. Speed 3 is too slow, so it moves up to 4 to 5. Speed 4 fits in exactly 8 hours, and the search then rules out everything below it.

Step by step

Start the range. left is 1 and right starts at piles[0]. The next two steps raise right to the biggest pile.
Loop over the piles with range, discarding the index with _, and set right to the larger of right and pile using the built-in max. Afterwards right is the biggest pile.
Remember a working speed. answer starts at right, which is known to work, so it is valid even before the search starts.
Loop while the range is non-empty. Go has no while; for left <= right does that job. With <=, a range holding one speed still gets that speed tried.
Pick the middle speed k as left + (right-left)/2. Integer division rounds down, and this form never overflows the way left + right could in a fixed-width integer.
Ask whether k is fast enough with hours(piles, k) <= h. The helper comes later in the file.
If it is, store k in answer and look for something slower by moving right to k - 1. Store first: the search never comes back to k, and it may be the smallest working speed.
If it isn't, k and every slower speed are too slow, so move left to k + 1.
Return answer. When the loop ends, every speed below it was ruled out.
Write the helper hours(piles []int, k int) int: total starts at 0, then a loop over the piles adds each pile's hours, and the function returns total.
Round up with integers only. A pile of pile bananas takes (pile + k - 1) / k hours. Adding k - 1 pushes any leftover bananas past the next multiple of k, while an exact multiple doesn't move.

The solution in Go

func minEatingSpeed(piles []int, h int) int {
	left, right := 1, piles[0]
	for _, pile := range piles {
		right = max(right, pile)
	}
	answer := right
	for left <= right {
		k := left + (right-left)/2
		if hours(piles, k) <= h {
			answer = k
			right = k - 1
		} else {
			left = k + 1
		}
	}
	return answer
}

func hours(piles []int, k int) int {
	total := 0
	for _, pile := range piles {
		total += (pile + k - 1) / k
	}
	return total
}

The Go details worth knowing:

Ceiling division. Integer / truncates, so 7 / 3 is 2 and forgets the last hour. (7 + 3 - 1) / 3 is 3, the right count for a pile of 7 at speed 3, while (6 + 3 - 1) / 3 is still 2 for a pile that divides evenly.
The built-in max. Since Go 1.21, max and min are built in and work on ordered types such as int. Nothing needs importing.
int is 64 bits. The total hours can be huge: 10^4 piles of 10^9 bananas at speed 1 take 10^13 hours. As an int that prints as 10000000000000. In a 32-bit integer the same sum wraps around silently: adding 10^9 ten thousand times in an int32 gives 1316134912. Go's int has no such problem here, but a type like int32 would.
Ignoring the index. for _, pile := range piles uses the blank identifier because Go refuses to compile an unused variable.
Helper order. Go doesn't need hours to be declared before minEatingSpeed uses it; functions at the top level of a file can appear in any order.

Complexity

Time: O(n log m). Finding the biggest pile is O(n). The binary search halves a range of at most m speeds, so it makes about log2(m) probes: roughly 30 for m = 10^9. Each probe calls hours, which visits every pile once.

Space: O(1). The function keeps a few integers and never copies the piles.

Edge cases and common mistakes

One pile. With [5] and h = 1 the answer is 5, since the pile must be eaten in one hour. With h = 5 it is 1.
As many hours as piles. When h equals the number of piles, every pile needs a single hour, so the answer is the biggest pile. For [30, 11, 23, 4, 20] and h = 5 that is 30.
A tight fit. For the same piles with h = 6 the answer is 23. At speed 23 the hours are 2 + 1 + 1 + 1 + 1 = 6; at 22 the pile of 23 takes 2 hours too, giving 2 + 1 + 2 + 1 + 1 = 7.
Rounding down per pile. Using pile / k instead of the ceiling undercounts the hours, so a too-slow speed looks fast enough and the answer comes out too small.
Rounding the total instead of each pile. Koko never eats from two piles in one hour. Dividing the sum of all bananas by k ignores that.
Losing the answer. Moving right to k - 1 without saving k first can throw away the smallest working speed.
Starting left at 0. Speed 0 would divide by zero in hours. The range starts at 1.
Huge piles. Two piles of 10^9 with h = 3 give 10^9: at any slower speed, such as 500000000, they take 2 + 2 = 4 hours.

Testing

piles = [3, 6, 7, 11], h = 8 gives 4.
piles = [30, 11, 23, 4, 20], h = 5 gives 30.
piles = [30, 11, 23, 4, 20], h = 6 gives 23.
piles = [5], h = 1 gives 5; with h = 5 it gives 1.
piles = [1, 1, 1], h = 3 gives 1.
piles = [1000000000, 1000000000], h = 3 gives 1000000000.
Ten thousand piles of 1000000000: h = 10000 gives 1000000000, and h = 1000000000 gives 10000.

Keep going with Go500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free