What is the brute force approach and complexity for Koko Eating Bananas?

Try speed 1, 2, 3, … and return the first one that finishes in time with time complexity O(M · N) and space complexity O(1).

What is the optimal approach and complexity for Koko Eating Bananas?

Binary search the speed range [1, max]; test each guess with the hours formula with optimal time complexity O(N log M) and space complexity O(1).

How do you identify the pattern for Koko Eating Bananas?

Look for key signals in the prompt: "smallest speed k such that she finishes in time" indicates "Minimum X such that something is possible" → binary search on the answer X.; "if a pile has fewer than k bananas, she waits" indicates Each pile costs ceil(p / k) hours. Given k, the total time is easy to compute → cheap feasibility check.; "eating faster never hurts" indicates If k works, k + 1 works. The check is monotonic, so the yes/no answers form ✗✗✗✓✓✓..

Koko Eating Bananas

Medium·LeetCode #875Basic Anchor

LeetCode

Jump:

30-Second Mental ModelBinary Search on the Answer (minimise speed)

Complexity:O(M · N)→O(N log M)

Key Insight

Every speed is either fast enough or too slow, and once a speed is fast enough, every faster speed is too. So the speeds 1 … max look like ✗✗✗✗✓✓✓✓. Binary search for the first ✓: test the middle speed, and throw away the half that can't hold the answer.

Core Validity Invariant

Speed k is fast enough when Σ ceil(p / k) ≤ h. A faster speed never needs more hours, so the answers look like ✗✗✗✓✓✓ and we search for the first ✓.

Problem

Koko has n piles of bananas. Pile i has piles[i] bananas. The guards come back in h hours.

Koko picks one eating speed k (bananas per hour) and keeps it. Every hour she picks one pile and eats k bananas from it. If the pile has fewer than k left, she finishes it and waits for the rest of that hour. She never moves to another pile in the same hour.

Return the smallest integer speed k that lets her finish every pile within h hours.

Input

An integer array piles and an integer h.

Output

One integer: the minimum eating speed.

Example 1

Input: piles = [3, 6, 7, 11], h = 8

Output: 4

At speed 4 the piles take 1 + 2 + 2 + 3 = 8 hours, which fits. At speed 3 they take 1 + 2 + 3 + 4 = 10 hours, which is too many.

Example 2

Input: piles = [30, 11, 23, 4, 20], h = 5

Output: 30

There are 5 piles and only 5 hours, so every pile must be finished in one hour. That needs speed 30, the biggest pile.

Example 3

Input: piles = [30, 11, 23, 4, 20], h = 6

Output: 23

At speed 23 the piles take 2 + 1 + 1 + 1 + 1 = 6 hours. At speed 22 the 23-pile also needs 2 hours, so the total is 7.

Constraints

• 1 ≤ piles.length ≤ 10^4
• piles.length ≤ h ≤ 10^9
• 1 ≤ piles[i] ≤ 10^9
• The total hours at a slow speed can reach 10^13 — use a 64-bit type for it.

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
If I tell you a speed, can you quickly work out how many hours Koko needs?
2.
How many hours does one pile of p bananas take at speed k? Why is it not just p / k?
3.
What is the slowest speed that could make sense? What is a speed that is always fast enough?
4.
If speed 5 is fast enough, is speed 6 also fast enough? If speed 5 is too slow, what about speed 4?
5.
Do I need to try every speed one by one, or can one check rule out many speeds at once?

Brute force approach

Idea

We want the smallest speed that works. So try speeds in increasing order: 1, 2, 3, … For each speed, add up the hours for every pile. The first speed whose total is at most h is the answer.

Thinking process

1
I can't pick a speed by looking at the piles directly, but I can test any speed: add up ceil(p / k) over all piles.
2
The answer is the smallest speed that passes this test.
3
The simplest way to find the smallest passing speed is to try 1, then 2, then 3, and stop at the first one that passes.
4
This always stops by max(piles), because at that speed every pile takes 1 hour.

Visual

Brute force tests speeds one by one. With a biggest pile of 10^9, this could take 10^9 tests.

Trying every speedpiles = [3, 6, 7, 11], h = 8step 1/4

speed

▲mid

ok?

✗

piles

hours

Brute force

speed: 1
hours needed: 3 + 6 + 7 + 11 = 27
h: 8
speeds tested: 1

hours(1) = 27 > 8

Speed 1 needs 27 hours, too many. Try the next speed.

Code & Implementation

brute.cpp

class Solution {
public:
    int minEatingSpeed(vector<int>& piles, int h) {
        // Try speeds 1, 2, 3, ... in order. The first speed that
        // finishes in time is the smallest one, so return it.
        // Speed max(piles) always works (1 hour per pile, and n <= h),
        // so the loop always stops.
        for (int k = 1; ; k++) {
            long long hours = 0;
            for (int p : piles) {
                hours += (p + (long long)k - 1) / k;   // ceil(p / k)
            }
            if (hours <= h) return k;
        }
    }
};

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        // Try speeds 1, 2, 3, ... in order. The first speed that
        // finishes in time is the smallest one, so return it.
        // Speed max(piles) always works (1 hour per pile, and n <= h),
        // so the loop always stops.
        for (int k = 1;; k++) {
            long hours = 0;
            for (int p : piles) {
                hours += (p + (long) k - 1) / k; // ceil(p / k)
            }
            if (hours <= h) return k;
        }
    }
}

class Solution:
    def minEatingSpeed(self, piles: list[int], h: int) -> int:
        # Try speeds 1, 2, 3, ... in order. The first speed that
        # finishes in time is the smallest one, so return it.
        # Speed max(piles) always works (1 hour per pile, and n <= h),
        # so the loop always stops.
        k = 1
        while True:
            hours = sum((p + k - 1) // k for p in piles)
            if hours <= h:
                return k
            k += 1

export function minEatingSpeed(piles: number[], h: number): number {
    // Try speeds 1, 2, 3, ... in order. The first speed that
    // finishes in time is the smallest one, so return it.
    // Speed max(piles) always works (1 hour per pile, and n <= h),
    // so the loop always stops.
    for (let k = 1; ; k++) {
        let hours = 0;
        for (const p of piles) {
            hours += Math.ceil(p / k);
        }
        if (hours <= h) return k;
    }
}

Complexity

Time O(M · N)Space O(1)

We may try up to max(piles) speeds, and each test walks all N piles. With max = 10^9 and N = 10^4, that is up to 10^13 steps — far too slow. M is the largest pile.

Optimized approach

Idea

Start from brute force

Brute force tests speed 1, then 2, then 3, … and learns only one fact from each test: "this speed works" or "this speed doesn't".

Find the repeated work

Each test actually tells us about many speeds, not one. If speed k is too slow, every speed below k is too slow too, so testing them is wasted work. Brute force throws that information away.

Define the state — what variables do I need?

lo, hi: The answer is somewhere in [lo, hi]. It starts as [1, max(piles)].
mid: The speed we test this round, the middle of [lo, hi].
hoursNeeded(mid): Sum of ceil(p / mid) over all piles: how long Koko needs at speed mid.

Define validity

Speed k is fast enough when Σ ceil(p / k) ≤ h. A faster speed never needs more hours, so the answers look like ✗✗✗✓✓✓ and we search for the first ✓.

Define the transitions — when does each pointer move, and why is it safe?

hoursNeeded(mid) ≤ h

hi = mid

mid works, so the answer is mid or something slower. Keep mid in the range (it might be the answer). Every speed above mid also works but is not the smallest, so drop them.

hoursNeeded(mid) > h

lo = mid + 1

mid is too slow. Every slower speed needs at least as many hours, so it is too slow too. The answer must be above mid.

lo == hi

return lo

Only one speed is left in the range, and the range always holds the answer.

What does the current window add to the answer?

Each test removes half of the speeds that are still possible. The range [lo, hi] always contains the smallest working speed, so when it shrinks to one value, that value is the answer.

Code & Implementation

optimal.cpp

class Solution {
    // Hours Koko needs at speed k. A pile of p bananas takes ceil(p / k) hours.
    // long long: up to 10^4 piles of 10^9 bananas at speed 1 is 10^13 hours.
    long long hoursNeeded(vector<int>& piles, int k) {
        long long hours = 0;
        for (int p : piles) {
            hours += (p + (long long)k - 1) / k;   // ceil(p / k) without floating point
        }
        return hours;
    }

public:
    int minEatingSpeed(vector<int>& piles, int h) {
        // Candidate speeds: [1, max(piles)].
        // 1 is the slowest legal speed; max(piles) always works (1 hour per pile).
        int lo = 1, hi = *max_element(piles.begin(), piles.end());

        // Loop style: while (lo < hi), hi = mid, lo = mid + 1.
        // [lo, hi] always contains the answer; we stop when one speed is left.
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (hoursNeeded(piles, mid) <= h) {
                hi = mid;        // mid works -> the answer is mid or slower
            } else {
                lo = mid + 1;    // mid is too slow -> every speed <= mid is too slow
            }
        }
        return lo;
    }
};

class Solution {
    // Hours Koko needs at speed k. A pile of p bananas takes ceil(p / k) hours.
    // long: up to 10^4 piles of 10^9 bananas at speed 1 is 10^13 hours.
    private long hoursNeeded(int[] piles, int k) {
        long hours = 0;
        for (int p : piles) {
            hours += (p + (long) k - 1) / k; // ceil(p / k) without floating point
        }
        return hours;
    }

    public int minEatingSpeed(int[] piles, int h) {
        // Candidate speeds: [1, max(piles)].
        // 1 is the slowest legal speed; max(piles) always works (1 hour per pile).
        int lo = 1;
        int hi = 0;
        for (int p : piles) {
            hi = Math.max(hi, p);
        }

        // Loop style: while (lo < hi), hi = mid, lo = mid + 1.
        // [lo, hi] always contains the answer; we stop when one speed is left.
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (hoursNeeded(piles, mid) <= h) {
                hi = mid; // mid works -> the answer is mid or slower
            } else {
                lo = mid + 1; // mid is too slow -> every speed <= mid is too slow
            }
        }
        return lo;
    }
}

class Solution:
    def minEatingSpeed(self, piles: list[int], h: int) -> int:
        # Hours Koko needs at speed k. A pile of p bananas takes ceil(p / k) hours.
        def hoursNeeded(k: int) -> int:
            return sum((p + k - 1) // k for p in piles)

        # Candidate speeds: [1, max(piles)].
        # 1 is the slowest legal speed; max(piles) always works (1 hour per pile).
        lo, hi = 1, max(piles)

        # Loop style: while (lo < hi), hi = mid, lo = mid + 1.
        # [lo, hi] always contains the answer; we stop when one speed is left.
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if hoursNeeded(mid) <= h:
                hi = mid  # mid works -> the answer is mid or slower
            else:
                lo = mid + 1  # mid is too slow -> every speed <= mid is too slow

        return lo

function hoursNeeded(piles: number[], k: number): number {
    let hours = 0;
    for (const p of piles) {
        hours += Math.ceil(p / k);
    }
    return hours;
}

export function minEatingSpeed(piles: number[], h: number): number {
    // Candidate speeds: [1, max(piles)].
    // 1 is the slowest legal speed; max(piles) always works (1 hour per pile).
    let lo = 1;
    let hi = 0;
    for (const p of piles) {
        hi = Math.max(hi, p);
    }

    // Loop style: while (lo < hi), hi = mid, lo = mid + 1.
    // [lo, hi] always contains the answer; we stop when one speed is left.
    while (lo < hi) {
        const mid = Math.floor(lo + (hi - lo) / 2);
        if (hoursNeeded(piles, mid) <= h) {
            hi = mid; // mid works -> the answer is mid or slower
        } else {
            lo = mid + 1; // mid is too slow -> every speed <= mid is too slow
        }
    }
    return lo;
}

Complexity

Time O(N log M)Space O(1)

About log₂(10^9) ≈ 30 guesses, each with an O(N) check. With N = 10^4 that is about 3·10^5 steps. M is the largest pile.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Try speed 1, 2, 3, … and return the first one that finishes in time	O(M · N)	O(1)
Optimal	Binary search the speed range [1, max]; test each guess with the hours formula	O(N log M)	O(1)

Why does this belong to this pattern?

Clues in the problem statement

“smallest speed k such that she finishes in time”"Minimum X such that something is possible" → binary search on the answer X.
“if a pile has fewer than k bananas, she waits”Each pile costs ceil(p / k) hours. Given k, the total time is easy to compute → cheap feasibility check.
“eating faster never hurts”If k works, k + 1 works. The check is monotonic, so the yes/no answers form ✗✗✗✓✓✓.

Minimise a number+easy check for a fixed guess+check is monotonic→Binary Search on the Answer (minimise speed)

This is the anchor problem for searching the answer space. Nothing in the input is sorted, and we never search the piles array. We search the range of possible speeds, and the check is a simple formula: Σ ceil(p / k) ≤ h. The next problems keep the same shape but change the check: a greedy fill (Ship Packages, Split Array) or counting runs of neighbours (Bouquets).

Don't make this mistake

Pattern confusion: binary searching the piles array

✗ sort(piles.begin(), piles.end()); // binary search for some index in piles ...

✓ int lo = 1, hi = *max_element(piles.begin(), piles.end()); // binary search on the speed

The answer is a speed, not a pile. Example 1's answer is 4, which is not even in [3, 6, 7, 11]. We search the range of possible answers, and use the piles only inside the check.

Starting the range at 0

✗ int lo = 0, hi = maxPile;

✓ int lo = 1, hi = maxPile;

Speed 0 makes no sense, and if mid ever becomes 0, p / mid divides by zero and the program crashes. The slowest real speed is 1.

Using p / k (rounding down) for the hours

✗ hours += p / k;

✓ hours += (p + (long long)k - 1) / k; // ceil(p / k)

A pile of 7 at speed 4 takes 2 hours (4, then 3), but 7 / 4 is 1. Integer division rounds down, so you would think slow speeds are fast enough and return an answer that is too small.

Overflowing int

✗ int hours = 0; hours += (p + k - 1) / k;

✓ long long hours = 0; hours += (p + (long long)k - 1) / k;

At speed 1, 10^4 piles of 10^9 bananas need 10^13 hours, far past the int limit (about 2.1·10^9). Even p + k - 1 alone can overflow when both are near 10^9.

Mixing loop styles

✗ while (lo <= hi) { ... hi = mid; ... }

✓ while (lo < hi) { ... hi = mid; else lo = mid + 1; }

With lo <= hi, when lo == hi == mid and mid works, hi = mid changes nothing and the loop never ends. Pick one style: lo < hi with hi = mid, or lo <= hi with hi = mid − 1 and a separate ans variable.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Binary Search translate into production architectures and low-level memory mechanics.

LLD Real-World Story

Order Book Price Level Matching

std::lower_bound lookup in sorted price ticks for limit orders.

Explore Track

C++ Internals

CPU Branch Prediction & Cache Efficiency

Branch mispredictions in binary search and branchless mid-point arithmetic.

Explore Track

Capacity To Ship Packages Within D Days