LESSON 335 OF 540 · BINARY SEARCH

Koko Eating Bananas in Scala: O(n log m) Binary Search on the Speed

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

Koko Eating Bananas in Scala, explained

Problem overview

The method minEatingSpeed receives an array piles of banana counts and an integer h, the hours Koko has. She picks a speed k, bananas per hour. Each hour she chooses one pile and eats up to k bananas from it; if the pile is smaller, she finishes it and wastes the rest of the hour. A pile of p bananas therefore takes p / k hours, rounded up. The method returns the smallest k that finishes all piles within h hours.

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

Approach: binary search on the answer

The speed has a limited range. The slowest useful speed is 1. The fastest we ever need is the biggest pile, piles.max: at that speed every pile takes one hour, and since h is at least the number of piles, it always fits. So the answer lies between 1 and piles.max.

Trying every speed in that range would take O(n · m) time, where m is the biggest pile. The key observation is that the speeds are ordered: if Koko finishes at speed k, she finishes at any faster speed too, and if she doesn't, no slower speed works either. The speeds turn from "too slow" to "fast enough" exactly once, and binary search finds where. We search over answers instead of over array positions.

Each test of a speed needs a helper, hours(piles, k), which adds up the hours of all the piles in O(n). Binary search tests about log2(m) speeds, so the total is O(n log m): around 30 tests for piles of up to a billion bananas.

Step by step

Set the range. left is 1 and right is piles.max, both vars. Both ends are inclusive candidates.
Start answer at right. The biggest pile always works, so answer holds a valid speed before the search begins. It will hold the smallest working speed found so far.
Loop while left <= right. When they are equal, one speed is still untried.
Pick the middle speed k = left + (right - left) / 2. Integer division rounds down, and this form can't overflow.
Test the speed with hours(piles, k) <= h.
If it works, save k in answer first, then look for something slower with right = k - 1. The search never returns to k, and it may be the best speed there is.
If it is too slow, so is every slower speed: left = k + 1.
Return answer after the loop. Every speed below it was ruled out as too slow.
Write the helper hours, taking the piles and a speed k and returning a Long.
Start total at 0L, a var. The L makes it a Long.
Loop over the piles, since Koko never eats from two piles in one hour and each pile adds its own hours.
Add the pile's hours, rounded up, using only integers: (pile + k - 1) / k.
Return total.

The solution in Scala

class Solution {
    def minEatingSpeed(piles: Array[Int], 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
            }
        }
        answer
    }

    def hours(piles: Array[Int], k: Int): Long = {
        var total = 0L
        for (pile <- piles) {
            total += (pile + k - 1) / k
        }
        total
    }
}

The Scala details worth a closer look:

Rounding up with integers. Integer division rounds down, so 7 / 3 is 2 and forgets the last hour. Adding k - 1 first pushes any leftover past the next multiple of k: (7 + 2) / 3 is 3. An exact multiple doesn't move: (6 + 2) / 3 is still 2. No Math.ceil or Double is needed.
Long for the total. At speed 1, 10,000 piles of a billion bananas take 10,000,000,000,000 hours, far beyond what an Int holds (about 2.1 billion). total starts as 0L, and total += (pile + k - 1) / k adds an Int to a Long, which stays a Long. With a plain Int counter, that same sum wraps silently to 1316134912, a number unrelated to the real count.
Comparing Long with Int. hours(piles, k) <= h compares a Long with an Int; Scala widens the Int, so no conversion is needed.
The last expression is the value. answer and total stand alone on the last line of their methods, which is how Scala returns them.
piles.max returns the largest element and throws an exception on an empty array. The constraints guarantee at least one pile.
The helper is a method of the class, so minEatingSpeed calls it by name.

Complexity

Time: O(n log m). The search range has m candidate speeds and halves on every pass, so there are about log2(m) passes. Each pass calls hours, which visits all n piles once.

Space: O(1). Only a few integers and the running Long total are kept.

Edge cases and common mistakes

One pile. With piles = [1000000000] and h = 1 the answer is 1000000000. With the same pile and h = 1000000000 it is 1. Both work without special cases.
As many hours as piles. For [30, 11, 23, 4, 20] and h = 5, every pile must take exactly one hour, so the answer is the biggest pile, 30. This is why right starts at piles.max.
A pile that takes two hours at the answer. For the same piles and h = 6, speed 23 takes 2 + 1 + 1 + 1 + 1 = 6 hours. At 22 the pile of 23 still takes 2 hours, and the total is 7, so the answer is 23.
Rounding down. Using pile / k alone undercounts every pile that isn't an exact multiple, and the search returns a speed that is too slow.
Overflow in the hours. A 32-bit total gives a wrong answer for large inputs: the hours at speed 1 for ten thousand piles of a billion bananas wrap around to 1316134912, which has nothing to do with the real count, and the comparison with h becomes meaningless. Keeping the total a Long avoids it.
Overflow in pile + k - 1. This sum is an Int. It stays safe because both pile and k are at most a billion, so the sum is below 2 billion.
Forgetting to save answer. If right = k - 1 runs without storing k, the best speed can be lost, because the search moves past it.

Testing

piles = [3, 6, 7, 11], h = 8 gives 4. The hours at speeds 1, 2, 3 and 4 are 27, 15, 10 and 8.
piles = [30, 11, 23, 4, 20], h = 5 gives 30.
piles = [30, 11, 23, 4, 20], h = 6 gives 23.
piles = [1], h = 1 gives 1.
10,000 piles of 1000000000 bananas with h = 1000000000 gives 10000.

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

Start learning free