Start learning free

LESSON 335 OF 540 · BINARY SEARCH

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

    TYPESCRIPT · BINARY SEARCH

    Koko Eating Bananas in TypeScript, explained

    Problem overview

    Koko has several piles of bananas, piles[i] in pile i, and h hours before the guards come back. She picks a speed k, in bananas per hour. Each hour she works on one pile and eats up to k bananas from it. If the pile has fewer than k, she finishes it and wastes the rest of that hour. A pile of p bananas therefore takes p / k hours, rounded up.

    The method minEatingSpeed(piles, h) returns the smallest whole speed that finishes every pile within h hours.

    For piles = [3, 6, 7, 11] and h = 8, speed 4 takes 1 + 2 + 2 + 3 = 8 hours, which is just in time, and speed 3 takes 1 + 2 + 3 + 4 = 10, which is too long. The answer is 4. For [30, 11, 23, 4, 20] with h = 5 there are as many hours as piles, so each pile must go in one hour and the speed has to match the biggest pile: 30. With h = 6 the answer is 23.

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

    Approach: binary search on the answer

    The simplest idea tries speeds 1, 2, 3 and so on until one fits. With piles of up to a billion bananas, that can mean a billion attempts, each costing a pass over the piles.

    The key observation is that the speeds are ordered in a useful way. If Koko finishes in time at speed k, she also finishes at any faster speed. If she doesn't, no slower speed works either. So going from speed 1 upwards, the speeds are "too slow" up to some point and "fast enough" from there on, and the answer is the first fast-enough one. A question with a yes/no answer that switches only once is exactly what binary search handles, and here we search over speeds instead of over array positions.

    The search range is 1 to the biggest pile. At the biggest pile's speed every pile takes one hour, and there are never more piles than hours, so that speed always works and no answer is bigger. Each probe asks: how many hours do all the piles take at speed k? That count comes from a small helper, hours. Since the range holds up to m speeds and halves every time, there are about log2(m) probes, each costing O(n).

    For the first example, the search probes speeds 6, 3 and 4. They need 6, 10 and 8 hours, which are compared with h = 8: speed 6 is fast enough, so a slower speed is tried; speed 3 is too slow; speed 4 is fast enough. Nothing is left below 4 and above 3, so 4 is the answer.

    Step by step

    1. Set the range with left = 1 and right = Math.max(...piles). The spread ...piles turns the array into separate arguments, so Math.max sees every pile.
    2. Remember a speed that works. answer starts at right, which is known to work, so the method has a valid result even before the first probe.
    3. Loop while left <= right: when they are equal, one speed is still untried.
    4. Take the middle speed k as left + (right - left) / 2 rounded down with Math.floor, because a speed is a whole number and / in TypeScript gives a float.
    5. Ask the helper how many hours speed k needs, and compare with h. The call goes through this, because hours is a method of the class.
    6. If it fits, store k in answer first, then look for something slower with right = k - 1. The store must come first: the search never returns to k, and it may be the smallest speed that works.
    7. If it doesn't fit, k and every slower speed are too slow, so left = k + 1.
    8. Return answer. When the loop ends, every speed below it was ruled out.
    9. Write hours(piles, k) as a separate method, which keeps the search short: it only asks whether a speed is fast enough.
    10. Sum with total, starting at 0, over each pile with for...of. Koko never eats from two piles in the same hour, so each pile adds its own hours.
    11. Round up with whole numbers only: add k - 1 to the pile and round the division down. Return total.

    The solution in TypeScript

    class Solution {
    minEatingSpeed(piles: number[], h: number): number {
        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: number[], k: number): number {
        let total = 0;
        for (const pile of piles) {
            total += Math.floor((pile + k - 1) / k);
        }
        return total;
    }
}

    TypeScript details worth knowing

    Rounding up. There is no integer division in TypeScript: 7 / 3 is 2.333.... The expression Math.floor((pile + k - 1) / k) rounds up using only whole numbers. For a pile of 7 and speed 3, (7 + 2) / 3 is exactly 3, while plain 7 / 3 rounded down gives 2 and forgets the last hour. For an exact multiple such as 6, (6 + 2) / 3 is 2.67, which still rounds down to 2, so nothing extra is added. Math.ceil(pile / k) gives the same results here, since both values stay far below the point where doubles lose precision.

    Large totals. A number is a double, so there is no 32-bit overflow. With 10,000 piles of a billion bananas, speed 1 needs 10,000,000,000,000 hours (ten trillion), and hours returns exactly that. Whole numbers stay exact up to 2^53, about nine quadrillion, so this is safe. Languages with 32-bit integers would need a wider type for this sum.

    The spread. Math.max(...piles) passes every pile as an argument. It is fine for the sizes in this lesson, up to 10,000 piles. Math.max(piles) without the spread would give NaN for an array of several piles, because an array is not a number.

    The annotations number[] and number disappear when the code is compiled to JavaScript. They help the compiler catch mistakes but change nothing at run time.

    Tracing the search

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

    leftrightkhours at speed kaction
    111666 <= 8: answer = 6, right = 5
    1531010 > 8: left = 4
    45488 <= 8: answer = 4, right = 3

    Now left is 4 and right is 3, the loop ends, and the method returns 4. For comparison, hours gives 27, 15, 10, 8, 8, 6, 5 and 4 at speeds 1, 2, 3, 4, 5, 6, 7 and 11. The count never goes up as the speed grows, which is the property the search relies on.

    Complexity

    Time: O(n log m). The range 1 to m halves on every pass, so there are about log2(m) passes: about 30 when m is a billion. Each pass calls hours, which visits all n piles once.

    Space: O(1). A few numbers; hours keeps one running total.

    Edge cases and common mistakes

    • One pile. With [5] and h = 1 the answer is 5; with h = 5 it is 1. A single pile of a billion with h = 1 gives 1,000,000,000.
    • Rounding down instead of up. Without the k - 1 trick, each pile loses its last partial hour, the totals come out too small, and the search settles on a speed that is too slow.
    • Starting left at 0. Speed 0 would divide by zero. A speed is at least 1.
    • Losing the best speed. If answer isn't saved before right moves, the loop can end without remembering the last speed that worked.
    • Using left < right. The last remaining speed would never be tried.
    • Forgetting this. inside the class. Calling hours(piles, k) alone refers to a function that doesn't exist.

    Testing

    The lesson's code gives these results:

    minEatingSpeed([3, 6, 7, 11], 8)        -> 4
minEatingSpeed([30, 11, 23, 4, 20], 5)  -> 30
minEatingSpeed([30, 11, 23, 4, 20], 6)  -> 23
minEatingSpeed([5], 1)                  -> 5
minEatingSpeed([5], 5)                  -> 1
minEatingSpeed([1000000000], 1)         -> 1000000000
minEatingSpeed([1, 1, 1], 3)            -> 1
    Keep going with TypeScript500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free