Koko Eating Bananas

Q: What is the time complexity of Koko Eating Bananas?

The binary search runs in O(n log m) time, where n is the number of piles and m the largest pile. Each check reads every pile once, and the range of speeds halves after each check, so there are about log2(m) checks: 30 when m = 10^9 . The extra space is O(1) .

Q: Why does binary search work on the eating speed?

Binary search needs a yes or no question whose answers are sorted. "Can Koko finish at speed k?" is one: a faster speed never needs more hours, because each pile's p / k rounded up can only shrink as k grows. So every speed below the answer fails and every speed from the answer up succeeds, and the search finds the boundary.

Q: What are the lower and upper bounds for the speed?

The upper bound is the largest pile: at that speed every pile takes exactly one hour, and h is at least the number of piles, so it always fits. A faster speed still needs one hour per pile, so searching above it gains nothing. The lower bound is 1, and you can tighten it to the total number of bananas divided by h , rounded up, because Koko eats at most k bananas an hour.

Q: How do you divide and round up with integers?

Use (p + k-1) / k with integer division. Adding k-1 pushes any remainder over the next multiple of k , and an exact multiple stays where it is: 10 at speed 4 gives 13 / 4 = 3 , and 8 at speed 4 gives 11 / 4 = 2 . It avoids floating point, where large values can round the wrong way.

MediumBinary search

+10

Koko has n piles of bananas, where piles[i] is the number of bananas in pile i, and h hours before the guards come back. She picks one eating speed k, a whole number of bananas per hour, and keeps it. Each hour she eats k bananas from one pile; if that pile has fewer than k left, she finishes it and rests until the hour is over. Return the smallest speed k that lets her finish every pile within h hours.

Function

minEatingSpeed(piles: integer-array, h: integer) → integer

pilesinteger-array: the number of bananas in each pile
hinteger: the number of hours Koko has
Returnsinteger: the smallest whole eating speed, in bananas per hour, that finishes every pile within h hours

Constraints

1 ≤ piles.length ≤ 5000
1 ≤ piles[i] ≤ 10⁹
piles.length ≤ h ≤ 10⁹, so an answer always exists.

Examples

Input: piles = [4, 10, 7, 3]h = 6
Output: 5
Explanation: At speed 5 the piles 4, 10, 7 and 3 take 1, 2, 2 and 1 hours: 6 in total, which fits. At speed 4 they take 1, 3, 2 and 1 hours, which is 7, one hour too many.

+22 hidden tests on Submit

Follow-up

A twin problem: Koko has d days and eats whole piles in the given order, as many piles a day as fit in a daily limit of k bananas. What is the smallest k, and which two parts of your binary search change?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

The answer here is a speed, not a position in the array, and that hides the binary search. Checking one speed takes a single pass over the piles. The checks also line up in order: if speed k finishes in time, every faster speed does too. So you can binary search over the speeds from 1 to the largest pile and need about 30 checks, where trying speeds one by one can need a billion.

Try every speed from 1 upward

Correct, but does not finish on the largest tests

Intuition

Start with one question: how long does a pile of p bananas take at speed k? Koko eats k an hour and never moves to another pile inside the same hour, so the pile takes p / k hours rounded up. A pile of 10 at speed 4 takes 3 hours: 4, 4, then 2 and a rest. Add that up over all the piles and compare the total with h.

Now try the speeds in order, 1, 2, 3, and so on, and return the first one whose total fits in h. It is the smallest by construction, since every slower speed was tried and failed. The loop always stops: at the largest pile's speed each pile takes one hour, and h is at least the number of piles.

The trouble is how far the loop can run. With 5000 piles of nearly 10^9 bananas and h = 5000, the answer is close to 10^9, so the loop runs about a billion times and each check reads all 5000 piles: about 5 × 10^12 steps. Here m is the largest pile.

Algorithm

Set speed = 1.
Count the hours at this speed: for each pile add (pile + speed-1) / speed, using a 64-bit total.
If the total is at most h, return speed.
Otherwise add 1 to speed and count again.

def minEatingSpeed(piles, h):
    speed = 1
    while True:
        hours = 0
        for pile in piles:
            hours += (pile + speed - 1) // speed  # a started pile costs a whole hour
        if hours <= h:
            return speed
        speed += 1

Binary search on the speed

Intuition

Think of every speed from 1 to the largest pile as a row of answers to the question "does this speed finish in time?". As the speed grows, each pile takes the same number of hours or fewer, so the total can only go down. The row therefore reads no, no, no, then yes from the answer onward, with no going back. You are looking for the first yes, and a sorted row of no and yes is exactly what binary search splits in half.

Keep a range lo to hi that always holds the answer. It starts at 1 and the largest pile, which is safe because the largest pile's speed takes one hour per pile and h covers that. Check the middle speed mid. If it fits, the answer is mid or slower, so set hi = mid and keep mid in the range. If it does not fit, every slower speed fails too, so set lo = mid + 1. When lo meets hi, that speed is the answer.

Trace the first example, piles 4, 10, 7, 3 with h = 6. The range is 1 to 10. Speed 5 takes 1 + 2 + 2 + 1 = 6 hours, which fits, so the range becomes 1 to 5. Speed 3 takes 2 + 4 + 3 + 1 = 10 hours, too many, so the range becomes 4 to 5. Speed 4 takes 1 + 3 + 2 + 1 = 7 hours, still too many, so the range becomes 5 to 5, and the answer is 5.

Each check halves the range, so a range of up to 10^9 speeds needs about 30 checks. At 5000 piles a check, that is about 150000 steps instead of trillions.

Algorithm

Set lo = 1 and hi to the largest pile.
While lo < hi, take mid = lo + (hi - lo) / 2.
Count the hours at speed mid: add (pile + mid-1) / mid for every pile, in a 64-bit total.
If the total is at most h, set hi = mid; otherwise set lo = mid + 1.
When the loop ends, return lo.

def minEatingSpeed(piles, h):
    lo, hi = 1, max(piles)  # the largest pile always works: one hour per pile
    while lo < hi:
        mid = lo + (hi - lo) // 2
        hours = 0
        for pile in piles:
            hours += (pile + mid - 1) // mid
        if hours <= h:
            hi = mid  # mid works, so the answer is mid or slower
        else:
            lo = mid + 1  # mid is too slow, so the answer is faster
    return lo

Pitfalls and edge cases

The search itself is short. The bugs hide in the hour count and in the edges of the range.

Overflowing the hour count. At speed 1, 5000 piles of 10^9 bananas take 5 × 10^12 hours, far past the 32-bit limit of about 2.1 × 10^9. A wrapped total can come out small and let a speed that is too slow pass the check. Count in a 64-bit integer, or stop counting as soon as the total passes h.
Rounding the wrong way. Integer division rounds down, so 10 / 4 gives 2, yet that pile takes 3 hours. Round up with (pile + k-1) / k.
Starting the range at 0. Then mid can be 0 and the hour count divides by zero. The slowest real speed is 1.
Moving hi to mid - 1 when mid fits. That can throw away the answer itself. When you search for the first speed that works, keep mid with hi = mid and loop while lo < hi.
Starting hi below the largest pile. Speeds below it can all fail when h equals the number of piles, so the search would return a speed that does not work.

Frequently asked questions4

What is the time complexity of Koko Eating Bananas?

The binary search runs in O(n log m) time, where n is the number of piles and m the largest pile. Each check reads every pile once, and the range of speeds halves after each check, so there are about log2(m) checks: 30 when m = 10^9. The extra space is O(1).

Why does binary search work on the eating speed?

Binary search needs a yes or no question whose answers are sorted. "Can Koko finish at speed k?" is one: a faster speed never needs more hours, because each pile's p / k rounded up can only shrink as k grows. So every speed below the answer fails and every speed from the answer up succeeds, and the search finds the boundary.

What are the lower and upper bounds for the speed?

The upper bound is the largest pile: at that speed every pile takes exactly one hour, and h is at least the number of piles, so it always fits. A faster speed still needs one hour per pile, so searching above it gains nothing. The lower bound is 1, and you can tighten it to the total number of bananas divided by h, rounded up, because Koko eats at most k bananas an hour.

How do you divide and round up with integers?

Use (p + k-1) / k with integer division. Adding k-1 pushes any remainder over the next multiple of k, and an exact multiple stays where it is: 10 at speed 4 gives 13 / 4 = 3, and 8 at speed 4 gives 11 / 4 = 2. It avoids floating point, where large values can round the wrong way.

Python

def minEatingSpeed(piles, h):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

piles = [4, 10, 7, 3]
h = 6

Expected