Coding interview problems › Binary Search

🔍 Binary Search Medium

Koko Eating Bananas (Binary Search on the Answer)

Koko Eating Bananas explained: binary search on the answer to find the minimum speed that finishes in h hours, tested Python, mistakes and a live visual.

Also searched as: binary search on answer · minimum eating speed · binary search on answer space problems

🔍

Try it live Free

Binary Search

In the binary search lab, watch how each comparison throws away half the range; here the "array" is the list of candidate speeds and each look asks whether a speed is fast enough.

Open the playground →

The problem

There are several piles of bananas, piles[i] in pile i. Each hour Koko picks one pile and eats up to k bananas from it (if the pile has fewer, she finishes it and waits for the next hour). Find the smallest integer speed k that lets her finish every pile within h hours. Assume h is at least the number of piles.

Inputpiles = [3, 6, 7, 11], h = 8
Output4

At speed 4 the piles take 1 + 2 + 2 + 3 = 8 hours; speed 3 needs 10.

The key insight

You are not searching an array; you are searching the range of possible answers, speeds from 1 to max(piles). The check "can she finish at speed k?" is monotonic: if speed k works, every faster speed also works. So binary search for the first speed where the check turns true.

Brute force first: Trying speeds 1, 2, 3 and so on until one works costs O(max(piles) · n), far too slow when piles hold up to a billion bananas.

Step-by-step approach

  1. Define hours(k) = sum of ceil(p / k) over all piles, computed as (p + k - 1) // k.
  2. Set lo = 1 and hi = max(piles); speed max(piles) always finishes in len(piles) hours.
  3. While lo < hi, take mid = (lo + hi) // 2.
  4. If hours(mid) <= h, mid works, so the answer is mid or smaller: hi = mid.
  5. Otherwise mid is too slow: lo = mid + 1.
  6. Return lo.

Python solution

PYTHON 3tested
def min_eating_speed(piles, h):
    def hours(k):
        return sum((p + k - 1) // k for p in piles)   # ceil(p / k)

    lo, hi = 1, max(piles)
    while lo < hi:
        mid = (lo + hi) // 2
        if hours(mid) <= h:     # fast enough: try slower
            hi = mid
        else:                   # too slow
            lo = mid + 1
    return lo

Complexity

TimeO(n log M)
SpaceO(1)

There are O(log M) binary search steps, where M is the largest pile, and each step sums over all n piles.

Common mistakes

Frequently asked questions

What is the time and space complexity?

O(n log M) time, where n is the number of piles and M is the largest pile, and O(1) extra space.

How do I recognise a binary-search-on-the-answer problem?

Look for wording like minimum speed, minimum capacity or smallest maximum, plus a yes or no check that flips only once as the answer grows. Ship Packages Within D Days and Split Array Largest Sum use the same template.

Why is max(piles) a safe upper bound?

At that speed every pile is eaten in one hour, so the total is len(piles) hours, which fits because h is at least the number of piles.

Can I compute the ceiling with math.ceil(p / k)?

It works for typical inputs, but floating-point division can misround huge values. The integer form (p + k - 1) // k is exact and avoids that risk.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Binary Search Binary Search lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.