DSA sheet · Binary Search · Binary search on answer

Koko Eating Bananas

This is the first problem of a new pattern called binary search on answer. Until now we ran binary search on the array we were given. Here the array is not where we search. We search over the possible answers (all the speeds Koko could eat at), a range that we decide ourselves. The teacher first solves it the slow way (try every speed from 1 upward), shows why it gets TLE, and then turns the same idea into binary search. Learn this one properly: problems 15 to 22 all follow the same recipe.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting
• Part A · Brute force: try every speed from 1 upward
• Part B · Optimal: binary search on the speed
• Part C · Revision page

Part 0 · Before starting

Why binary search works at all

Binary search does not really need a "sorted array". What it needs is a yes/no question whose answers line up like this: all the "no"s on one side, all the "yes"s on the other side, with one switch point in the middle. Then one look at the middle tells us which half can't contain the switch point, and we throw that half away. A sorted array is just one case of this: "is arr[i] >= target?" is no, no, no, yes, yes.

A yes/no question with this "no…no then yes…yes" shape is called monotonic (it changes direction only once, it never flips back).

low, high, mid

• low: the smallest value still worth looking at.
• high: the biggest value still worth looking at.
• mid: the value in the middle, the one we test now.
• We loop while low <= high. With <=, the last single value (when low and high meet) still gets tested.

Why mid = low + (high - low) // 2 and not (low + high) // 2?

Both give the same number. The teacher always writes the first form because in Java/C++ a normal int stops at about 2.1 × 10⁹. If low and high are both near 10⁹, then low + high goes past that limit and overflows (wraps around to a garbage negative number). high - low is never bigger than high, so the first form is always safe.

In Python, integers never overflow, so both forms work. We still write the safe form so the habit carries over to interviews in any language.

The new pattern: binary search on answer

In some problems the question asks for the smallest (or largest) number that makes something possible: the minimum speed, the minimum capacity, the minimum number of days. For those:

1. The answer range. Decide the smallest answer that could ever make sense (low) and the biggest one we'd ever need (high). The answer must be somewhere in [low, high]. This range is a list of whole numbers, so it is already sorted, even when the input array is not.
2. The check function. Write check(x): "if the answer were x, would it work?" It returns True or False.
3. Monotonic. If x works, then every bigger x also works (eating faster never makes you slower). So over the range, check gives no no no yes yes yes. One switch point.
4. Which side to keep. We want the first yes (the minimum). If check(mid) is yes, mid might be the answer, but a smaller one might also work, so save mid and go left. If it's no, mid and everything below it is useless, so go right.

answer range:  low ......................................... high
check(x):       no   no   no   no  YES  YES  YES  YES  YES
                                   ^
                          the first YES = the minimum answer

Ceiling division (we need it here)

Ceiling of a number means "round it up to the next whole number": ceil(1.5) = 2, ceil(1.1) = 2, ceil(3.0) = 3. Normal integer division p // k rounds down (gives the floor). The trick to round up using only integers is (p + k - 1) // k. Adding k - 1 pushes any leftover over to the next whole number, but it can't push an exact division over.

Part A · Brute force: try every speed from 1 upward

LeetCode 875

1The question in simple words

There are n piles of bananas. Pile i has piles[i] bananas. The guards will be back in h hours. Koko picks an eating speed k = bananas per hour. Find the smallest speed k that lets her finish all the piles within h hours.

One special rule: each hour she sits at one pile. If that pile has fewer than k bananas left, she finishes it and wastes the rest of that hour. She can't move to the next pile in the same hour.

The inputs are numbers of bananas and time (h). The output is a speed. So the thing we return is not even an element of the array. That's the first hint that this is "binary search on answer".

2What the constraints tell us

• 1 <= piles.length <= 10⁴ → at least one pile, so no empty-array case.
• piles.length <= h <= 10⁹ → h is never smaller than the number of piles. Even in the worst case she has at least 1 hour per pile, so an answer always exists (we never return −1).
• 1 <= piles[i] <= 10⁹ → one pile can be huge. A speed up to 10⁹ may be needed, so the range of speeds is up to 10⁹ long.
• The values fit in a normal int, so the inputs themselves don't overflow. But see the overflow point in Part B step 9 (the hours sum and p + k − 1 can overflow in Java).

3Intuition: how would you do it by hand?

Forget binary search for a moment. If someone asked you for the minimum speed, you would simply try speeds one by one, starting from the slowest: "speed 1, does she finish in time? No. Speed 2? No. Speed 3? No. Speed 4? Yes!" The first speed that works is the smallest one, because we tried them in increasing order.

Notice what we are looping over: not the array, but a range of speeds we chose ourselves. That's the key idea of the whole pattern.

4Building the logic from examples

How many hours does one speed take?

For each pile, the hours needed = bananas ÷ speed, rounded up (because a half-used hour is still a full hour gone). Add this up over all piles. The teacher works it out for speeds 1, 2, 3 and 4 with piles = [3, 6, 7, 11], h = 8:

Each time the total was more than 8, we had to speed up: a higher speed means fewer hours. At speed 4 the total is exactly 8.

Where should the speeds start and stop? (low and high)

The teacher spends real time on this, because choosing low and high well is exactly what the interviewer wants to see.

• Low = 1. Speed 0 means she never eats, so 1 is the slowest speed that makes sense.
• High = max(piles). She found it by trial: try speed 11 (the biggest pile). Every pile takes 1 hour (3/11, 6/11, 7/11 are all "0.something", which rounds up to 1; 11/11 is exactly 1). Total 4 hours. Now try 12 → still 1 hour per pile → 4 hours. 13 → 4 hours again. Going faster than the biggest pile doesn't help any more, because she can never finish a pile in less than one hour. So we never need a speed above max(piles).

Also, since 11 already works and we want the minimum, we would only ever look left of 11 (10, 9, 8…), never right. So max(piles) is a safe ceiling.

5Approach steps

1. Set low = 1, high = max(piles).
2. For each speed k from low to high:
3. Add up the hours: for each pile p, add (p + k - 1) // k.
4. If the total is <= h, return k. It's the first that works, so it's the smallest.

6Code (Python)

class Solution:
    def minEatingSpeed(self, piles, h):
        low = 1
        high = max(piles)
        for k in range(low, high + 1):        # k = the speed we try
            hours = 0
            for p in piles:
                hours += (p + k - 1) // k     # ceil(p / k)
            if hours <= h:                    # finished in time
                return k                      # first one = smallest
        return high                           # never reached: high always works

7Code line by line

8Dry run

piles = [3, 6, 7, 11], h = 8, so low = 1, high = 11.

1. k = 1 → 3 + 6 + 7 + 11 = 27 hours → 27 > 8 no.
2. k = 2 → 2 + 3 + 4 + 6 = 15 → no.
3. k = 3 → 1 + 2 + 3 + 4 = 10 → no.
4. k = 4 → 1 + 2 + 2 + 3 = 8 → 8 <= 8 yes → return 4 ✓

speed k :   1    2    3    4    5    6    7    8    9   10   11
hours   :  27   15   10    8    8    6    5    5    5    5    4
<= 8 ?  :  no   no   no  YES  YES  YES  YES  YES  YES  YES  YES
                          ^ the first YES = 4

Look at the "hours" row: it only goes down (or stays) as speed goes up. That is why the yes/no row switches only once. Keep this picture in mind for Part B.

9Complexity & remember

• Time O(max(piles) × n). The outer loop can run up to 10⁹ times (piles[i] can be 10⁹), and each try walks all n ≤ 10⁴ piles. That is about 10⁹ × 10⁴ = 10¹³ operations. Far above the ~10⁸ limit → TLE.
• Space O(1).

Part B · Optimal: binary search on the speed

1The question

Same question as Part A. We keep the same range and the same "hours" calculation. We only change how we walk through the range.

2Constraints

The same. The one that matters now: the range 1 … max(piles) can be 10⁹ long. Walking it one by one is the problem. Halving it is the fix: log₂(10⁹) ≈ 30 steps.

3Intuition: the range of speeds is already sorted

In Part A the outer loop goes 1, 2, 3, … max. Those speeds sit on a number line in sorted order, and the "can she finish?" answer is no…no then yes…yes along that line. So instead of checking every speed in turn, pick the middle speed, check it, and throw away half the range. The inner loop (adding up the hours) stays the same, because we really do have to look at every pile to know the total time.

To keep the code clean, the teacher moves the hours calculation into its own function, canEat(piles, h, k), which returns True if speed k is fast enough.

4Building the decisions from examples

Check mid. If it works → save it and go left

The teacher takes the number line 1 … 11 and checks a speed near the middle, 5: hours = 1 + 2 + 2 + 3 = 8 → 8 ≤ 8, it works. Is 5 the answer? Maybe. We don't know yet whether some speed on the left (smaller) also works. So:

• Don't throw mid away: save it in ans, because it is a valid answer so far.
• Then look only at the left half: high = mid - 1.

Check mid. If it doesn't work → go right

Suppose speed 5 had needed 10 hours. Then 5 is not a valid answer, so don't save it. Every speed below 5 is even slower, so those fail too. The answer must be bigger: low = mid + 1.

What to start ans with

Start it as high (= max(piles)). The constraint h ≥ n means max(piles) always works (every pile takes 1 hour, n hours ≤ h). Her extreme example: one pile of 11 bananas and h = 1. The only speed that works is 11 = max(piles). So in the worst case max(piles) is the answer, and it's a safe starting value. (Any starting value is fine really, since the loop will overwrite it.)

5Approach steps

1. low = 1, high = max(piles), ans = high.
2. While low <= high: mid = low + (high - low) // 2 (mid is the speed to test).
3. If canEat(mid): ans = mid, then high = mid - 1 (look for a smaller speed).
4. Else: low = mid + 1 (need a faster speed).
5. Return ans.

6Code (Python)

class Solution:
    def minEatingSpeed(self, piles, h):
        low = 1
        high = max(piles)
        ans = high                         # max(piles) always works
        while low <= high:
            mid = low + (high - low) // 2  # mid = the speed k we test
            if self.canEat(piles, h, mid):
                ans = mid                  # works: remember it
                high = mid - 1             # try smaller speeds
            else:
                low = mid + 1              # too slow: try faster
        return ans

    def canEat(self, piles, h, k):
        hours = 0
        for p in piles:
            hours += (p + k - 1) // k      # ceil(p / k)
        return hours <= h

class Solution:
    def minEatingSpeed(self, piles, h):
        low, high = 1, max(piles)
        while low < high:                  # stop when one speed is left
            mid = low + (high - low) // 2
            hours = sum((p + mid - 1) // mid for p in piles)
            if hours <= h:
                high = mid                 # mid works, keep it in range
            else:
                low = mid + 1
        return low                         # low == high == the answer

7Code line by line

8Dry run (hand table)

piles = [3, 6, 7, 11], h = 8. Range 1 … 11, ans = 11.

The range of speeds shrinking (yellow = mid, grey = thrown away):

Only 3 checks instead of 4 in brute force here, but for a range of 10⁹ it's about 30 checks instead of up to a billion.

9Complexity & remember

• Time O(n × log(max(piles))). The range 1 … max(piles) is halved each step, so about log₂(10⁹) ≈ 30 steps. Each step calls canEat, which walks all n ≤ 10⁴ piles. Total ≈ 30 × 10⁴ = 3 × 10⁵ → passes easily.
• Space O(1).
• Overflow (Java/C++ only): the teacher's Java code first failed and she switched to long. Two places can overflow there: p + k - 1 (p up to 10⁹ plus k up to 10⁹ is past the int limit), and the hours total (10⁴ piles × up to 10⁹ hours each). Python ints grow as needed, so our code has no such problem.

Part C · Revision page

s = Solution()
print(s.minEatingSpeed([3, 6, 7, 11], 8))          # 4
print(s.minEatingSpeed([30, 11, 23, 4, 20], 5))    # 30
print(s.minEatingSpeed([30, 11, 23, 4, 20], 6))    # 23
print(s.minEatingSpeed([10, 10], 20))              # 1  (below min(piles)!)
print(s.minEatingSpeed([11], 1))                   # 11 (worst case = max)
print(s.minEatingSpeed([10**9], 2))                # 500000000

Based on this video: Koko Eating Bananas | Binary Search on Answer