Start learning free

LESSON 335 OF 540 · BINARY SEARCH

Koko Eating Bananas in Kotlin: 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 13

Guided

Ctrl + Enter to check

KOTLIN · BINARY SEARCH

Koko Eating Bananas in Kotlin, explained

Problem overview

Koko has several piles of bananas and h hours before the guards return. She picks a speed of k bananas per hour. Each hour she chooses one pile and eats up to k bananas from it; if the pile has fewer, she finishes it and wastes the rest of that hour. So a pile of p bananas takes p / k hours, rounded up.

The function minEatingSpeed(piles: IntArray, h: Int): Int returns the smallest speed that finishes every pile within h hours.

With piles = [3, 6, 7, 11] and h = 8, speed 4 takes 1 + 2 + 2 + 3 = 8 hours, just in time, while speed 3 takes 1 + 2 + 3 + 4 = 10 hours. The answer is 4.

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 speed

The simple method tries speeds 1, 2, 3, and so on, and stops at the first one that works. Each try costs O(n), and the answer can be as large as the biggest pile, so that is O(n · m): too slow when piles reach a billion bananas.

The speeds have a useful shape. If Koko finishes in time at speed k, she finishes at any faster speed as well. If she doesn't, no slower speed works either. So going from speed 1 upward, the speeds are first too slow and then fast enough, and the switch happens only once. Whenever answers flip from "no" to "yes" exactly once, binary search can find the flip point. Here the search runs over the range of possible speeds rather than over an array.

The range is easy to bound. Speed 1 is the slowest sensible speed. The biggest pile is the fastest speed that's ever useful: at that speed every pile takes one hour, and since there are never more piles than hours, it always works. So the answer lies between 1 and piles.max(), and the search needs about log2(m) rounds, each costing one pass over the piles.

Step by step

Set the range. left starts at 1 and right at piles.max(). Both are vars, since the search moves them.
Remember a working speed. answer starts at right, which is known to work, so it is valid even before the first test.
Loop while left <= right. When they are equal, one speed is still untested.
Pick a middle speed k as left + (right - left) / 2.
Test it with a helper, hours(piles, k), which returns the total hours at that speed. If it is at most h, the speed works.
If it works, save k in answer and search for something slower by moving right to k - 1. Save first: the search never returns to k, and it may be the best speed.
If it doesn't, every slower speed fails too, so move left to k + 1.
Return answer once the range is empty. Every speed below it was ruled out.
Write the helper hours. It takes the piles and a speed and returns a Long.
Start a Long total with 0L.
Loop over the piles. Koko never eats from two piles in one hour, so each pile adds its own hours.
Round up with integers only: (pile + k - 1) / k.
Return the total.

The solution in Kotlin

class Solution {
    fun minEatingSpeed(piles: IntArray, h: Int): Int {
        var left = 1
        var right = piles.max()
        var answer = right
        while (left <= right) {
            val k = left + (right - left) / 2
            if (hours(piles, k) <= h) {
                answer = k
                right = k - 1
            } else {
                left = k + 1
            }
        }
        return answer
    }

    fun hours(piles: IntArray, k: Int): Long {
        var total = 0L
        for (pile in piles) {
            total += (pile + k - 1) / k
        }
        return total
    }
}

Kotlin details worth a look:

Rounding up. Integer division truncates, so 7 / 3 is 2, which forgets the last hour. Adding k - 1 first pushes any leftover past the next multiple: (7 + 3 - 1) / 3 is 3. An exact multiple doesn't move, so (6 + 3 - 1) / 3 is still 2. The sum pile + k - 1 stays below 2,000,000,000 for piles and speeds up to a billion, so it fits in an Int.
Why the helper returns a Long. With 10,000 piles of 1,000,000,000 bananas, speed 1 needs 10,000,000,000,000 hours. An Int tops out near 2.1 billion; summing those piles in an Int gives 1316134912 instead of 10,000,000,000,000. Declaring total with 0L makes it a Long.
Adding an Int to a Long. total += ... with an Int on the right compiles, because Long has a plus overload for Int and the result is a Long.
Comparing Long with Int. hours(piles, k) <= h compiles directly, since Long has a compareTo overload for Int. Mixed == between the two types is not allowed, but <= is.
piles.max(). On an IntArray it returns the largest element as a plain Int. It throws on an empty array, which the constraints rule out.
Two functions in one class. hours is a member of Solution, so minEatingSpeed calls it by name, and it may appear below its first use.

Complexity

Time: O(n log m). The search range holds m speeds and halves every round, so there are about log2(m) rounds, around 30 for a billion. Each round calls hours, which makes one pass over the n piles.

Space: O(1). Only a few numbers are kept.

Edge cases and common mistakes

One pile. [5] with h = 1 returns 5, and [1000000000] with h = 2 returns 500000000.
As many hours as piles. Every pile must take exactly one hour, so the answer is the biggest pile: [30, 11, 23, 4, 20] with h = 5 returns 30.
Rounding down instead of up. Plain pile / k undercounts every pile that doesn't divide evenly, so the function would accept speeds that are too slow.
Overflow in the total. Summing hours in an Int wraps silently to a wrong, possibly negative, number, and the comparison with h then gives a wrong yes. Use a Long.
Losing the answer. If answer isn't saved before right moves, the loop can end without remembering the speed that worked.
Using left < right. The final candidate speed would never be tested.

Testing

Trace for piles = [3, 6, 7, 11] and h = 8:

left=1 right=11 k=6 hours=6
left=1 right=5 k=3 hours=10
left=4 right=5 k=4 hours=8

Speed 6 works (6 hours), so the range moves down. Speed 3 needs 10 hours, so the range moves up. Speed 4 needs exactly 8 hours and works; the range then becomes empty, and the answer is 4.

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.
10,000 piles of 1,000,000,000 with h = 10000 gives 1000000000.

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

Start learning free