Start learning free

LESSON 331 OF 536 · BINARY SEARCH

Koko Eating Bananas in Python: 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 a list 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

    PYTHON · BINARY SEARCH

    Koko Eating Bananas in Python, explained

    Problem overview

    Koko has several piles of bananas, piles[i] in pile i, and h hours before the guards return. At a speed of k bananas per hour she eats from one pile each hour. If the pile has fewer than k bananas she finishes it and wastes the rest of that hour. So a pile of p bananas takes p / k hours, rounded up.

    The method minEatingSpeed returns the smallest integer k that lets her eat everything 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 each pile must go in one hour and the speed is the biggest pile, 30. With h = 6 the answer is 23.

    Approach: binary search on the answer

    The unusual thing here is what gets searched. There is no sorted list to look into. Instead, the candidate speeds 1, 2, 3, ... form an ordered range, and a single question sorts them: does speed k finish within h hours?

    That question has a useful shape. If Koko finishes at speed k, she finishes at any faster speed too. If she doesn't, no slower speed works either. So going from speed 1 upward, the answer to the question is "no" for a while and then "yes" forever. For the first example:

    speed  1  2  3  4  5  11
hours 27 15 10  8  8   4

    With h = 8, speeds 1 to 3 are too slow, and speeds 4 and up are fast enough. The answer is the first "yes", and binary search can find where the answer flips to "yes" without trying every speed.

    The range to search is small. The slowest sensible speed is 1. The fastest that could ever be needed is the biggest pile, because at that speed every pile takes one hour, and the constraints say h is at least the number of piles. No answer is bigger than max(piles), so the search runs over 1 to max(piles). That is why the time is O(n log m), with m the biggest pile: about log m speeds are tried, and each try reads all n piles.

    Here is the search on the first example:

    left=1 right=11 k=6 hours=6 ok=True
left=1 right=5 k=3 hours=10 ok=False
left=4 right=5 k=4 hours=8 ok=True

    Speed 6 works, so it is stored as a candidate and the search looks at slower speeds. Speed 3 is too slow, so the search looks above it. Speed 4 works. That leaves nothing smaller to try, and the stored answer is 4.

    Step by step

    1. Set the range. left is 1 and right is max(piles), both set in one tuple assignment.
    2. Start answer at right. That speed always works, so answer holds a valid speed before the search even begins.
    3. Loop while left <= right. When both ends are the same speed, that speed still needs a try.
    4. Pick k halfway between the ends with floor division.
    5. Ask the question by calling a helper, self.hours(piles, k), and comparing the result with h. The helper is written afterwards; the search only needs to know it exists.
    6. If the speed works, save it in answer and move right to k - 1 to look for something slower. Save first: the search never returns to k, and it may be the best speed there is.
    7. Otherwise, k and every slower speed are too slow, so left becomes k + 1.
    8. After the loop, return answer. Every speed below it was ruled out.
    9. Write the helper hours(self, piles, k) inside the class, after minEatingSpeed.
    10. Start total at 0 and loop over the piles. Koko never eats from two piles in the same hour, so each pile adds its own hours.
    11. Round up with integers. Add pile + k - 1 and floor-divide by k.
    12. Return total.

    The solution in Python

    class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        left, right = 1, max(piles)
        answer = right
        while left <= right:
            k = left + (right - left) // 2
            if self.hours(piles, k) <= h:
                answer = k
                right = k - 1
            else:
                left = k + 1
        return answer
    def hours(self, piles, k):
        total = 0
        for pile in piles:
            total += (pile + k - 1) // k
        return total

    Python details worth a closer look:

    • Rounding up without floats. // 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. A pile that is an exact multiple doesn't move: (6 + 2) // 3 is still 2. The expression math.ceil(pile / k) gives the same numbers but goes through a float, so the integer form is the safer habit.
    • Big numbers are fine. Python integers grow as needed. With 10,000 piles of 1,000,000,000 bananas, speed 1 takes 10000000000000 hours, which a 32-bit integer couldn't hold, and hours returns it without trouble.
    • Calling a method of the class. hours is a method, so the search calls it as self.hours(...). Writing hours(piles, k) alone would raise a NameError.
    • Order of definitions. minEatingSpeed uses hours before the code of hours appears in the file. That is fine: the name is looked up when the method runs, by which time the class is complete.
    • Floor division of the midpoint. left + (right - left) // 2 keeps k an integer. With / it would be a float, and the rounding in hours would be wrong.

    Complexity

    Time: O(n log m). The range holds m = max(piles) speeds, and each pass of the loop discards half of them, so there are about log2(m) passes: roughly 30 when m is 1,000,000,000. Each pass calls hours, which makes one pass over the n piles.

    Space: O(1). The search keeps a few integers, and hours only adds up a total.

    Edge cases and common mistakes

    • One pile. For [10] with h = 10 the answer is 1, because one banana per hour for 10 hours is enough. With h = 1 it is 10, the whole pile in one hour.
    • Exactly as many hours as piles. The answer is max(piles), as in the second example. In that case the search never finds anything better than its starting answer.
    • Plenty of time. For [1, 1, 1, 1] the answer is 1 whether h is 4 or 100. The speed can't go below 1, which is why left starts there.
    • Rounding down. Using pile // k alone undercounts every pile that doesn't divide evenly, so the helper reports too few hours and the method returns a speed that is too slow.
    • Losing the answer. Moving right to k - 1 without storing k first throws away a speed that may be the smallest one that works.
    • Searching the wrong direction. If the speed works, look lower; if it doesn't, look higher. Swapping the two moves breaks the search.
    • Using left < right. The last remaining speed is never tried, so the smallest working speed can be missed when it is that last one.

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