Koko Eating Bananas — The Warehouse Deadline

Boss 3: The Warehouse Deadline

Bosses 1 and 2 had something in common: a sorted collection sat in front of you, and you searched it.

This boss hands you a few piles of bananas and a clock. No sorted array. Nothing to index into. And yet the fastest solution is binary search.

If that sounds impossible, good. This is the boss where the weapon changes shape.

The story

Koko works the night shift at a fruit warehouse. Tonight's job: four piles of banana crates sitting on the dock.

piles = [3, 6, 7, 11]

The truck leaves in 8 hours. Rules of the warehouse:

• Koko picks one speed k and sticks with it all night. k crates per hour, no changing mid-shift.
• Each hour, she works on one pile only. If the pile has fewer than k crates left, she finishes it and, well, the rest of that hour is hers. She can't start the next pile early.

Koko is efficient, but she's not a fan of rushing.

"If I set k to 11, I clear one pile per hour and finish in 4. But why sweat? The truck doesn't leave for 8 hours. What's the laziest speed that still gets everything on the truck?"

Try k = 4 in your head. Pile of 3 takes 1 hour. Pile of 6 takes 2 hours (4, then the last 2). Pile of 7 takes 2. Pile of 11 takes 3. Total: 8 hours. Exactly on time.

Try k = 3: that's 1 + 2 + 3 + 4 = 10 hours. Truck's gone. So for this dock, the answer is 4.

Fine for four piles. Now imagine fifty piles, some holding a million crates. How does Koko find her number?

The problem, dressed up properly

Koko loves to eat bananas. There are n piles of bananas, the i-th pile has piles[i] bananas. The guards have gone and will come back in h hours.

Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile and eats k bananas from it. If the pile has fewer than k bananas, she eats all of them instead and will not eat any more bananas during this hour.

Return the minimum integer k such that she can eat all the bananas within h hours.

Same math, more bananas, fewer crates. LeetCode 875.

The naive attempt

Try every speed starting from 1, return the first one that works.

import math
 
def min_eating_speed(piles, h):
    k = 1
    while True:
        hours = sum(math.ceil(pile / k) for pile in piles)
        if hours <= h:
            return k
        k += 1

Correct, and doomed. If the biggest pile has a billion crates and the deadline is tight, this crawls through up to a billion candidate speeds, each costing a full O(n) pass. That's O(n * max(piles)). The warehouse shift ends before your program does.

The weapon: search the answer space

Here's the mental flip. Stop looking for an array. Ask two questions instead.

Question 1: for a given speed k, can Koko finish in time? That's cheap to check:

def can_finish(k):
    return sum((pile + k - 1) // k for pile in piles) <= h

Question 2: how does that answer behave as k grows? Faster speeds never hurt. If speed 4 works, speed 5 works, and 6, and every speed after. If speed 3 fails, so did 2 and 1. Line up all speeds from 1 to max(piles) and label each one:

k:           1      2      3      4      5      6  ...  11
can_finish:  false  false  false  true   true   true ... true

One unbroken run of false, then one unbroken run of true. That's called monotonic, and it's the only license binary search ever needed. Sorted arrays were just the most famous example. Koko's answer is the first true, the boundary between the two runs, and you can find a boundary by halving.

Watching it work

piles = [3, 6, 7, 11], h = 8. Speeds range from 1 to 11.

step   lo   hi   mid   hours at mid          feasible?   move
1      1    11   6     1+1+2+2 = 6  ≤ 8      yes         hi = 6
2      1    6    3     1+2+3+4 = 10 > 8      no          lo = 4
3      4    6    5     1+2+2+3 = 8  ≤ 8      yes         hi = 5
4      4    5    4     1+2+2+3 = 8  ≤ 8      yes         hi = 4
       lo == hi == 4 → answer is 4 ✓

Watch what the moves mean. When mid works, we don't throw it away, it might be the answer, so hi = mid keeps it in range while discarding everything faster. When mid fails, it's dead for sure, so lo = mid + 1. The range shrinks until one speed remains: the slowest feasible one.

The code

def min_eating_speed(piles: list[int], h: int) -> int:
    def can_finish(k: int) -> bool:
        return sum((pile + k - 1) // k for pile in piles) <= h
 
    lo, hi = 1, max(piles)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if can_finish(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

Why is hi = max(piles) enough? Because at that speed every pile takes exactly one hour, and speed beyond that buys nothing, one pile per hour is the ceiling anyway. And lo = 1 because zero crates per hour finishes nothing.

The loop can't get stuck, by the way. mid = lo + (hi - lo) // 2 rounds down, so mid < hi always holds inside the loop, meaning both branches strictly shrink the range.

Gotchas

1. Ceiling division, not floor. A pile of 7 at speed 4 takes 2 hours, not 1. Writing pile // k undercounts and makes impossible schedules look fine. Use math.ceil(pile / k) or the integer trick (pile + k - 1) // k. The trick is preferred in most languages: no floats, no precision surprises on giant numbers.

2. Returning mid the first time something is feasible. Feasible means "fast enough", not "slowest possible". In the trace above, speed 6 was feasible on step 1, but the answer was 4. The loop must run until the range collapses.

3. Starting lo at 0. Speed zero divides by zero in the feasibility check, or loops forever, depending on how you wrote it. Answer-space bounds deserve a second of thought: smallest meaningful candidate, smallest sufficient ceiling.

4. Off-by-one in the moves. In this template it's always hi = mid and lo = mid + 1. Flip either one and you'll either discard the answer or spin forever on a two-element range.

Complexity

The search space has max(piles) candidate speeds, so the loop runs O(log max) times. Each iteration calls can_finish, a single O(n) pass over the piles.

Total: O(n log max(piles)). For 50 piles topping out at a billion crates, that's 50 * 30 = 1,500 operations. The naive version wanted tens of billions.

Boss down. XP gained.

Koko sets the dial to 4 and enjoys her spare minutes.

What you walked away with:

• Binary search doesn't need an array, it needs a monotonic yes/no question
• The recipe: define the answer range, write can_finish(k), search for the boundary
• The boundary template: while lo < hi, feasible means hi = mid, infeasible means lo = mid + 1
• Ceiling division without floats: (pile + k - 1) // k

This pattern is called search on answer, and once you see it, you see it everywhere: smallest ship capacity to clear cargo in d days, minimum days for bouquets, split array to minimize the largest sum. Different costumes, same monotonic boundary.

Next up: Boss 4 — The Night Shift Logbook. A guard's logbook is sorted by hour, but someone tore it at a random page and taped it back in the wrong order. Find the smallest entry without reading the whole thing. Binary search, on an array that's only mostly sorted.