Start learning free

LESSON 338 OF 543 · BINARY SEARCH

Koko Eating Bananas in Rust: Binary Search on the Answer, O(n log m)

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

    RUST · BINARY SEARCH

    Koko Eating Bananas in Rust, explained

    Problem overview

    Koko has several piles of bananas and h hours. At speed k, she spends each hour on one pile and eats up to k bananas from it. A pile of p bananas therefore takes p / k hours rounded up, because a last, smaller bite still costs a whole hour. min_eating_speed takes piles: Vec<i32> and h: i32 and returns the smallest integer speed that finishes everything within h hours.

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

    Approach: search the speeds, not the piles

    The brute force is to try speed 1, then 2, then 3, and stop at the first one that works. That can take up to the size of the biggest pile in attempts, and each attempt reads every pile.

    The key observation is that the speeds are ordered: if Koko finishes in time at speed k, she also finishes at any faster speed, and if she does not, no slower speed works either. So going from speed 1 upward, the speeds are "too slow" up to some point and "fast enough" from then on, with a single switch. Binary search finds that switch. It is a search on the answer: the thing being halved is the range of possible speeds.

    The range is 1 to the biggest pile. At the biggest pile's speed, every pile takes one hour, and since h is never less than the number of piles, that speed always works. No answer can be larger.

    For each candidate speed, a helper hours adds up the time of all the piles, which is O(n). With about log2(m) candidates, where m is the biggest pile, the total is O(n log m).

    Step by step

    1. Set the range. left is 1, the slowest speed. right is *piles.iter().max().unwrap(), the biggest pile. max() returns an Option holding a reference (None for an empty vector), unwrap() takes the reference out and * copies the number.
    2. Start answer at right. That speed is known to work, so answer is valid even before the search begins.
    3. Loop while left <= right. With <=, the last remaining speed is still tried.
    4. Take the middle speed: k = left + (right - left) / 2.
    5. Ask whether k is fast enough: Self::hours(&piles, k) <= h as i64. The & lends the vector instead of moving it into the call, and h as i64 gives both sides of the comparison the same type.
    6. If it is fast enough, store k in answer and look for something slower with right = k - 1. Store first: the search never returns to k, and it may be the smallest speed that works.
    7. Otherwise k and every slower speed are too slow, so left = k + 1.
    8. Return answer with no semicolon. When the loop ends, every speed below answer was too slow.
    9. Write the helper hours. It borrows the piles as a slice &[i32], takes the speed, and returns an i64. It starts a total: i64 at 0 and loops over the piles with the pattern &pile, which copies each number out of its reference.
    10. Round up with integers only. The hours for one pile are (pile + k - 1) / k. A pile of 7 at speed 3 takes 3 hours, and (7 + 2) / 3 is 3, while 7 / 3 alone is 2 and forgets the last bite. The result is turned into an i64 with as i64 before it is added.

    The search for piles = [3, 6, 7, 11] and h = 8, printing each round:

    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 takes 6 hours, which fits, so the answer is at most 6 and right becomes 5. Speed 3 takes 10 hours, which is too many, so left becomes 4. Speed 4 takes 8 hours and fits, so right becomes 3 and the loop ends with answer equal to 4.

    The solution in Rust

    impl Solution {
    fn min_eating_speed(piles: Vec<i32>, h: i32) -> i32 {
        let mut left = 1;
        let mut right = *piles.iter().max().unwrap();
        let mut answer = right;
        while left <= right {
            let k = left + (right - left) / 2;
            if Self::hours(&piles, k) <= h as i64 {
                answer = k;
                right = k - 1;
            } else {
                left = k + 1;
            }
        }
        answer
    }

    fn hours(piles: &[i32], k: i32) -> i64 {
        let mut total: i64 = 0;
        for &pile in piles {
            total += ((pile + k - 1) / k) as i64;
        }
        total
    }
}

    The Rust details worth a closer look:

    • Why i64 for the total. With 10,000 piles of 1,000,000,000 bananas, speed 1 takes 10,000,000,000,000 hours, far beyond what an i32 holds (about 2.1 billion). The helper returns exactly that number. An i32 total would wrap silently in a -O build: 10000 * 1_000_000_000 in i32 comes out as 1316134912. In a debug build the same overflow panics.
    • Why the pile can stay an i32. pile + k - 1 is at most about 2 billion, which still fits in an i32. Only the sum over many piles can get too big.
    • Slices. &piles is a &Vec<i32>, and Rust converts it to the &[i32] the helper asks for. The helper can read the numbers but not change or own them.
    • for &pile in piles. Iterating over a slice yields references. The pattern &pile copies each number out, so pile is an i32.
    • Associated function. hours has no self, so it is called as Self::hours.
    • Types of left and right. Both are inferred as i32, since right comes from the piles and k is passed to hours.

    Complexity

    Time: O(n log m). The search halves a range of at most m speeds, so it makes about log2(m) rounds, about 30 for a billion. Each round calls hours, which visits the n piles once.

    Space: O(1). The search keeps a few integers and the helper borrows the piles.

    Edge cases and common mistakes

    • One pile. [5] with h = 1 gives 5: the whole pile must go in one hour. With h = 5 it gives 1.
    • As many hours as piles. [30, 11, 23, 4, 20] with h = 5 gives 30, the biggest pile, because every pile must be finished in one hour.
    • A little extra time. The same piles with h = 6 give 23. At speed 22 the pile of 23 needs 2 hours, so the total is 7, one too many.
    • Rounding down. Using pile / k alone undercounts every pile that does not divide evenly, so slow speeds look faster than they are and the function returns too small an answer.
    • Overflow. Keep the total in an i64. For the largest input, speed 1 needs 10 trillion hours.
    • Forgetting to save answer. If you only move right, you lose the working speed when the search then moves past it.
    • Using left < right. When the range shrinks to one speed, that speed is never tested, so the search can miss the answer.

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