Start learning free

LESSON 331 OF 536 · BINARY SEARCH

Koko Eating Bananas in JavaScript: 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 <= 104, where n is the number of piles
  • n <= h <= 109
  • 1 <= piles[i] <= 109

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: 104 piles of 109 bananas take 1013 hours at speed 1, far more than a 32-bit integer can hold.

STEP 1 OF 13
    Ctrl + Enter to check

    JAVASCRIPT · BINARY SEARCH

    Koko Eating Bananas in JavaScript, 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 an eating speed k, in 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 she eats nothing else that hour. A pile of p bananas therefore takes p / k hours, rounded up.

    The method minEatingSpeed(piles, h) returns the smallest whole-number 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. For piles = [30, 11, 23, 4, 20] and h = 5 there are as many hours as piles, so every pile must take one hour and the speed has to be the biggest pile, 30. With h = 6 the answer drops to 23.

    The statement 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 array isn't sorted, and the thing to search for isn't a position in it. The thing to search for is the speed. Speeds run from 1 up to the biggest pile: no speed above the biggest pile is ever needed, because at that speed every pile already takes one hour, and h is never smaller than the number of piles.

    Trying every speed from 1 upward works, but with piles up to 10^9 it can take a billion tries, each costing O(n). The speeds have a useful structure, though. If Koko finishes in time at speed k, she also finishes at any faster speed. If she doesn't finish at k, no slower speed works either. So the speeds split into a block that is too slow, followed by a block that is fast enough, and we want the first speed of the second block. Binary search finds that boundary: test the middle speed, and discard the half that can't hold the boundary.

    To test a speed we need to know how many hours it takes. That is a separate helper, hours(piles, k), which keeps the search itself short: it only asks whether a speed is fast enough.

    Step by step

    1. Set the search range. left is the slowest speed, 1, and right is the biggest pile, Math.max(...piles). The spread ...piles turns the array into separate arguments for Math.max.
    2. Prepare answer. It holds the smallest working speed found so far. It starts at right, which is known to work, so the method has a valid result even before the search finds anything better.
    3. Loop while left <= right. When both ends meet, one speed is still left to test.
    4. Take the middle speed k as left plus half the distance to right, rounded down. A speed is a whole number, and / in JavaScript can leave a fraction.
    5. Ask whether k is fast enough: is this.hours(piles, k) <= h? The helper belongs to the class, so it is called through this.
    6. If it is fast enough, store k in answer first, then look for something slower by setting right = k - 1. Storing comes first because the search never returns to k, and it may be the best speed there is.
    7. Otherwise k is too slow, and so is every speed below it, so set left = k + 1.
    8. After the loop, return answer. Every speed below it was ruled out as too slow.
    9. Write the helper hours(piles, k) inside the class, after minEatingSpeed.
    10. Start a running total at 0.
    11. Loop over the piles with for...of. Koko never eats from two piles in the same hour, so each pile adds its own hours.
    12. Round up with whole numbers. Add k - 1 to the pile, divide by k and round down with Math.floor. Leftover bananas push the sum past the next multiple of k, and an exact multiple stays where it was.
    13. Return total.

    The solution in JavaScript

    class Solution {
    minEatingSpeed(piles, h) {
        let left = 1, right = Math.max(...piles);
        let answer = right;
        while (left <= right) {
            let k = Math.floor(left + (right - left) / 2);
            if (this.hours(piles, k) <= h) {
                answer = k;
                right = k - 1;
            } else {
                left = k + 1;
            }
        }
        return answer;
    }
    hours(piles, k) {
        let total = 0;
        for (let pile of piles) {
            total += Math.floor((pile + k - 1) / k);
        }
        return total;
    }
}

    The JavaScript details worth a closer look:

    • Rounding up. JavaScript's / always gives a fraction: 7 / 3 is 2.3333333333333335. Rounding that down gives 2, which forgets the last hour. The trick Math.floor((pile + k - 1) / k) gives 3. For an exact multiple, Math.floor((6 + 2) / 3) is still 2. Math.ceil(pile / k) would also work with numbers this size; the integer form just avoids fractions.
    • Big totals are safe. A JavaScript number is a double, which holds whole numbers exactly up to about 9 · 10^15. In the worst case, 10,000 piles of 10^9 bananas at speed 1 take 10^13 hours, which is exact: hours returns 10000000000000 for that input. In a language with 32-bit integers the same total would overflow.
    • The helper is a method. Inside a class, hours must be called as this.hours(...). Writing a bare hours(...) looks for a variable or a function of that name and throws a ReferenceError.
    • Math.max(...piles). It spreads every pile into an argument. That is fine for the 10,000 piles allowed here.
    • for...of with let. It walks the values of the array. A for...in loop would walk the indices as strings, which isn't what this loop needs.

    Tracing piles = [3, 6, 7, 11], h = 8

    leftrightkhours at kdecision
    11166fast enough: answer = 6, right = 5
    15310too slow: left = 4
    4548fast enough: answer = 4, right = 3

    Now left is 4 and right is 3, the loop ends, and the method returns 4.

    Complexity

    Time: O(n log m). The search range holds m speeds, where m is the biggest pile, and each pass halves it, so there are about log2(m) passes: around 30 for 10^9. Each pass calls hours, which visits every pile once, so it costs O(n).

    Space: O(1). The code keeps a few numbers. The spread in Math.max(...piles) briefly passes the piles as arguments, but it doesn't keep a copy of them.

    Edge cases and common mistakes

    • One pile. [5] with h = 1 returns 5: the whole pile must go in one hour. [10] with h = 2 returns 5.
    • Many hours. [1, 1, 1] with h = 100 returns 1, since speed 1 already fits. The search range shrinks toward the left end.
    • Exactly as many hours as piles. [1, 1, 1] with h = 3 also returns 1, and [30, 11, 23, 4, 20] with h = 5 returns 30.
    • Huge piles. [1000000000, 1000000000] with h = 2 returns 1000000000, and with h = 1000000000 it returns 2.
    • Not remembering the answer. Returning left or k after the loop is easy to get wrong. Saving k each time it works is simple and reliable.
    • Rounding down. Using Math.floor(pile / k) forgets the final partial hour and gives a speed that is too small.
    • Starting left at 0. A speed of 0 divides by zero: x / 0 is Infinity in JavaScript, which wrecks the arithmetic instead of raising an error. Speeds start at 1.

    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.
    • piles = [10], h = 2 gives 5.
    • piles = [1, 1, 1], h = 100 gives 1.
    Keep going with JavaScript500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free