Start learning free

LESSON 336 OF 541 · BINARY SEARCH

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

    SWIFT · BINARY SEARCH

    Koko Eating Bananas in Swift, explained

    Problem overview

    minEatingSpeed receives piles, an array of banana counts, and h, the number of hours Koko has. She picks a speed k bananas per hour. Each hour she works on one pile and eats up to k bananas from it; if the pile has fewer, she finishes it and wastes the rest of the hour. A pile of p bananas therefore takes p / k hours, rounded up. The function returns the smallest integer k that gets through all the piles 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 task asks for O(n log m) time, where n is the number of piles and m the biggest pile, and O(1) extra space.

    Approach: binary search on the speed

    The simple idea is to try speed 1, then 2, then 3, and stop at the first speed that works. That can take up to m attempts, and each attempt costs O(n), which is far too slow when a pile holds a billion bananas.

    The better idea uses one fact: if Koko finishes in time at speed k, she also finishes at any faster speed, and if she doesn't, no slower speed works either. So the speeds split into a block of "too slow" followed by a block of "fast enough", and the answer is the first speed of the second block. Binary search finds that boundary. The search runs over speeds, not over positions in the array, which is why it is called binary search on the answer.

    The search range is easy to set. The slowest sensible speed is 1. The fastest worth trying is the biggest pile: at that speed every pile takes one hour, and since there are never more piles than hours, it always works. No answer is ever larger. The range 1 to piles.max()! has about log2(m) halvings, around 30 for a billion.

    Each halving needs the total hours at one speed, which is a plain loop over the piles. That part lives in a helper method named hours.

    Step by step

    1. Set the range. Declare left as 1 and right as the biggest pile, both with var because the search moves them.
    2. Remember a speed that works. answer starts at right, which is known to be fast enough, so it holds a valid speed even before the search begins.
    3. Loop while left <= right. When they are equal, one speed is still untried.
    4. Take the middle speed k = left + (right - left) / 2.
    5. Ask the helper. If hours(piles, k) <= h, speed k finishes in time.
    6. Speed k works: store it in answer, then look for a slower one by moving right to k - 1. Store first: the search never returns to k, and it may be the smallest working speed.
    7. Speed k is too slow: in the else branch, move left to k + 1. Every slower speed fails too.
    8. After the loop every speed below answer has been ruled out, so return it.
    9. Write the helper hours inside the class. It takes the piles and a speed, both without argument labels, and returns an Int.
    10. Keep a running total in a var starting at 0.
    11. Loop over the piles with for pile in piles. Koko never eats from two piles in the same hour, so each pile adds its own hours.
    12. Round up with integers only. Add (pile + k - 1) / k. Adding k - 1 pushes any leftover bananas over the next multiple of k, while an exact multiple stays where it is.
    13. Return the total.

    The solution in Swift

    class Solution {
    func minEatingSpeed(_ piles: [Int], _ h: Int) -> Int {
        var left = 1, right = piles.max()!
        var answer = right
        while left <= right {
            let 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 {
        var total = 0
        for pile in piles {
            total += (pile + k - 1) / k
        }
        return total
    }
}

    Swift details worth knowing:

    • max() returns an optional. On an empty array [Int]().max() is nil. The lesson guarantees at least one pile, so the ! unwrap is safe here. On an empty array it would stop the program.
    • Integer rounding. / on two Int values truncates. For a pile of 7 at speed 3, 7 / 3 is 2 and forgets the last hour, while (7 + 2) / 3 is 3. For a pile of 6, (6 + 2) / 3 is still 2.
    • Big totals fit in Int. Int is 64 bits. With 10,000 piles of a billion bananas, speed 1 needs 10,000,000,000,000 hours, and the total fits. Swift stops the program on integer overflow instead of wrapping, so an Int32 total would be a real danger here, and Int avoids it.
    • Calling a method of the same class. Inside minEatingSpeed, hours(piles, k) is a call on self, so no prefix is needed. The method can be defined below the code that calls it.
    • Multiple vars on one line. var left = 1, right = piles.max()! declares two variables, both Int.

    Complexity

    Time: O(n log m). The range 1 to m halves on every pass, so the loop runs about log2(m) times. Each pass calls hours, which visits all n piles once. Finding the maximum at the start costs another O(n).

    Space: O(1). The code keeps a few integers. The helper doesn't build any array.

    Edge cases and common mistakes

    • Rounding down instead of up. Using pile / k undercounts every pile that doesn't divide evenly, so the function returns speeds that are too slow.
    • Exactly as many hours as piles. With piles = [30, 11, 23, 4, 20] and h = 5, every pile must take one hour, so the answer is the biggest pile, 30. This is why right starts at the maximum and answer starts there too.
    • One pile. [5] with h = 1 gives 5, and with h = 5 gives 1. A single pile of a billion with h = 2 gives 500,000,000.
    • Moving right before saving k. If the order of the two lines in the success branch is swapped, the value can be lost.
    • Returning left without tracking answer. That form also works if you are careful, but it is easy to be off by one. Saving each working speed is simpler to get right.
    • left = k or right = k. Without the + 1 and - 1, the range can stop shrinking and the loop never ends.

    Testing

    • piles = [3, 6, 7, 11], h = 8 gives 4. The helper returns 10 for speed 3 and 8 for speed 4.
    • piles = [30, 11, 23, 4, 20], h = 5 gives 30.
    • piles = [30, 11, 23, 4, 20], h = 6 gives 23. The helper returns 7 for speed 22 and 6 for speed 23.
    • piles = [5], h = 1 gives 5, and h = 5 gives 1.
    • piles = [1, 1, 1], h = 3 gives 1.

    On the first example the search tries 6 (6 hours, works, so right becomes 5), then 3 (10 hours, too slow, so left becomes 4), then 4 (8 hours, works, so right becomes 3) and stops with answer = 4.

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