875. Koko Eating Bananas (Medium)

Problem

Koko has n piles of bananas (array piles, where piles[i] is the count in pile i). Each hour she chooses one pile and eats up to k bananas from it. If the pile has fewer than k, she finishes the pile but doesn’t eat more bananas that hour.

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

Example

• piles = [3,6,7,11], h = 8 → 4
• piles = [30,11,23,4,20], h = 5 → 30
• piles = [30,11,23,4,20], h = 6 → 23

LeetCode 875 · Link · Medium

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, try every speed from 1 upward

Start at k = 1 and increment until she finishes in time.

Python

from math import ceil

def min_eating_speed(piles: list[int], h: int) -> int:
    k = 1
    while True:                                     # L1: loop up to max(piles) times
        hours = sum(ceil(p / k) for p in piles)    # L2: O(n) feasibility check
        if hours <= h:
            return k
        k += 1                                      # L3: O(1) increment

TypeScript

function minEatingSpeed(piles: number[], h: number): number {
    let k = 1;
    while (true) {                                                // L1: loop up to max(piles) times
        const hours = piles.reduce((s, p) => s + Math.ceil(p / k), 0);  // L2: O(n) feasibility
        if (hours <= h) return k;
        k++;                                                      // L3: O(1) increment
    }
}

Go

func minEatingSpeed(piles []int, h int) int {
    k := 1
    for {                                                    // L1: loop up to max(piles) times
        total := 0
        for _, p := range piles {
            total += (p + k - 1) / k                        // L2: O(n) feasibility check
        }
        if total <= h {
            return k
        }
        k++                                                  // L3: O(1) increment
    }
}

Swift

final class Solution {
    func minEatingSpeed(_ piles: [Int], _ h: Int) -> Int {
        var speed = 1
        while true {
            let hours = piles.reduce(0) { total, pile in
                total + (pile + speed - 1) / speed
            }
            if hours <= h { return speed }
            speed += 1
        }
    }
}

Where the time goes, line by line

Variables: n = len(piles), M = max(piles).

Line	Per-call cost	Times executed	Contribution
L1 (loop)	$O(1)$	up to M	$O(M)$
L2 (feasibility sum)	$O(n)$	up to M	$O(n · M)$ ← dominates
L3 (increment)	$O(1)$	up to M	$O(M)$

In the worst case k must reach max(piles) before succeeding. Each check scans all n piles.

Complexity

• Time: $O(n · max(piles)$) worst case, driven by L2.
• Space: $O(1)$.

Approach 2: Linear search from max downward (no improvement)

Starting from k = max(piles) and decrementing doesn’t help, we’d still do $O(max)$ iterations.

Python

from math import ceil

def min_eating_speed(piles, h):
    for k in range(max(piles), 0, -1):                  # L1: M iterations downward
        hours = sum(ceil(p / k) for p in piles)         # L2: O(n) feasibility check
        if hours > h:                                   # first failure: previous k was the answer
            return k + 1
    return 1

TypeScript

function minEatingSpeed(piles: number[], h: number): number {
    for (let k = Math.max(...piles); k >= 1; k--) {          // L1: M iterations downward
        const hours = piles.reduce((s, p) => s + Math.ceil(p / k), 0);  // L2: O(n) feasibility
        if (hours > h) return k + 1;                         // first failure: previous k was answer
    }
    return 1;
}

Go

func minEatingSpeed(piles []int, h int) int {
    maxPile := 0
    for _, p := range piles {
        if p > maxPile { maxPile = p }
    }
    for k := maxPile; k >= 1; k-- {            // L1: M iterations downward
        total := 0
        for _, p := range piles {
            total += (p + k - 1) / k           // L2: O(n) feasibility check
        }
        if total > h { return k + 1 }          // first failure: previous k was answer
    }
    return 1
}

Swift

final class Solution {
    func minEatingSpeed(_ piles: [Int], _ h: Int) -> Int {
        var speed = piles.max() ?? 1
        while speed >= 1 {
            let hours = piles.reduce(0) { total, pile in
                total + (pile + speed - 1) / speed
            }
            if hours > h { return speed + 1 }
            speed -= 1
        }
        return 1
    }
}

max(piles) always works (h ≥ n is guaranteed by the problem), so we walk down until the first speed that fails. Same $O(n · M)$ profile as Approach 1; just goes the other direction.

A genuine middle tier is the realization that feasibility is monotonic: if speed k works, every k' > k also works. That monotonicity is the signal for binary search.

Complexity

• Time: $O(n · max(piles)$).
• Space: $O(1)$.

Approach 3: Binary search on the answer (optimal)

The answer lives in [1, max(piles)]. Binary-search this range using a feasibility predicate hours_needed(k) ≤ h.

Python

from math import ceil

def min_eating_speed(piles: list[int], h: int) -> int:
    def hours(k: int) -> int:
        return sum(ceil(p / k) for p in piles)    # L1: O(n) per call

    lo, hi = 1, max(piles)                         # L2: O(n) to find max
    while lo < hi:                                  # L3: loop, O(log M) iterations
        mid = (lo + hi) // 2                       # L4: O(1) midpoint
        if hours(mid) <= h:                        # L5: O(n) feasibility check
            hi = mid                               # L6: O(1) mid works, try smaller
        else:
            lo = mid + 1                           # L7: O(1) too slow, need larger k
    return lo

TypeScript

function minEatingSpeed(piles: number[], h: number): number {
    function hours(k: number): number {
        return piles.reduce((sum, p) => sum + Math.ceil(p / k), 0);  // L1: O(n) per call
    }

    let lo = 1, hi = Math.max(...piles);             // L2: O(n) to find max
    while (lo < hi) {                                // L3: loop, O(log M) iterations
        const mid = (lo + hi) >> 1;                  // L4: O(1) midpoint
        if (hours(mid) <= h) hi = mid;               // L5/L6: mid works, try smaller
        else lo = mid + 1;                           // L7: too slow, need larger k
    }
    return lo;
}

Go

func minEatingSpeed(piles []int, h int) int {
    hours := func(k int) int {
        total := 0
        for _, p := range piles {
            total += (p + k - 1) / k               // L1: O(n) per call
        }
        return total
    }

    lo, hi := 1, 0
    for _, p := range piles {
        if p > hi { hi = p }                       // L2: O(n) to find max
    }
    for lo < hi {                                  // L3: loop, O(log M) iterations
        mid := (lo + hi) / 2                      // L4: O(1) midpoint
        if hours(mid) <= h {                       // L5: O(n) feasibility check
            hi = mid                              // L6: O(1) mid works, try smaller
        } else {
            lo = mid + 1                          // L7: O(1) too slow, need larger k
        }
    }
    return lo
}

Swift

final class Solution {
    func minEatingSpeed(_ piles: [Int], _ h: Int) -> Int {
        var low = 1
        var high = piles.max() ?? 1
        while low < high {
            let middle = low + (high - low) / 2
            let hours = piles.reduce(0) { total, pile in
                total + (pile + middle - 1) / middle
            }
            if hours <= h {
                high = middle
            } else {
                low = middle + 1
            }
        }
        return low
    }
}

Where the time goes, line by line

Variables: n = len(piles), M = max(piles).

Line	Per-call cost	Times executed	Contribution
L2 (find max)	$O(n)$	1	$O(n)$
L3 (loop)	$O(1)$	log M	$O(log M)$
L5 (feasibility check)	$O(n)$	log M	$O(n · log M)$ ← dominates
L6 or L7 (narrow)	$O(1)$	log M	$O(log M)$

The search space for k is [1, max(piles)], so the binary search runs log(max(piles)) steps. Each step calls hours(k) which sums over all n piles in $O(n)$.

Complexity

• Time: $O(n · log(max(piles)$)), driven by L5 ($O(n)$ feasibility check repeated log M times).
• Space: $O(1)$.

Integer-only hours (avoid float ceil)

ceil(p / k) can be replaced with (p + k - 1) // k to avoid floating point entirely:

def hours(k: int) -> int:
    return sum((p + k - 1) // k for p in piles)

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Swift notes

The Swift implementations use integer ceiling division, (pile + speed - 1) / speed, so feasibility never passes through Double. Int is 64-bit on the supported runner and Apple platforms, which gives the accumulated hour count room above the individual pile constraint.

Summary

Approach	Time	Space
Linear scan on k	$O(n · max(piles)$)	$O(1)$
Binary search on k	$O(n · log(max(piles)$))	$O(1)$

This is the template for every “minimum/maximum value that satisfies a monotonic predicate” problem. Once you recognize the monotonicity, you have the algorithm.

Adjacent problems: 1011 Capacity To Ship Packages, 410 Split Array Largest Sum, 1482 Minimum Days to Make Bouquets, 2226 Maximum Candies Allocated to K Children.

Test cases

Python

# Quick smoke tests - paste into a REPL or save as test_875.py and run.
# Uses the optimal Approach 3 implementation.

from math import ceil

def min_eating_speed(piles: list, h: int) -> int:
    def hours(k: int) -> int:
        return sum(ceil(p / k) for p in piles)

    lo, hi = 1, max(piles)
    while lo < hi:
        mid = (lo + hi) // 2
        if hours(mid) <= h:
            hi = mid
        else:
            lo = mid + 1
    return lo

def _run_tests():
    assert min_eating_speed([3, 6, 7, 11], 8) == 4
    assert min_eating_speed([30, 11, 23, 4, 20], 5) == 30
    assert min_eating_speed([30, 11, 23, 4, 20], 6) == 23
    assert min_eating_speed([1], 1) == 1              # single pile, exact fit
    assert min_eating_speed([1000000000], 2) == 500000000  # large pile, 2 hours
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

function minEatingSpeed(piles: number[], h: number): number {
    const hours = (k: number) => piles.reduce((s, p) => s + Math.ceil(p / k), 0);
    let lo = 1, hi = Math.max(...piles);
    while (lo < hi) {
        const mid = (lo + hi) >> 1;
        if (hours(mid) <= h) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

console.assert(minEatingSpeed([3, 6, 7, 11], 8) === 4);
console.assert(minEatingSpeed([30, 11, 23, 4, 20], 5) === 30);
console.assert(minEatingSpeed([30, 11, 23, 4, 20], 6) === 23);
console.assert(minEatingSpeed([1], 1) === 1);                      // single pile, exact fit
console.assert(minEatingSpeed([1000000000], 2) === 500000000);     // large pile, 2 hours
console.log("all tests pass");

Go

package main

import "fmt"

func minEatingSpeed(piles []int, h int) int {
    hours := func(k int) int {
        total := 0
        for _, p := range piles {
            total += (p + k - 1) / k
        }
        return total
    }
    lo, hi := 1, 0
    for _, p := range piles {
        if p > hi { hi = p }
    }
    for lo < hi {
        mid := (lo + hi) / 2
        if hours(mid) <= h {
            hi = mid
        } else {
            lo = mid + 1
        }
    }
    return lo
}

func main() {
    if minEatingSpeed([]int{3, 6, 7, 11}, 8) != 4             { panic("test 1") }
    if minEatingSpeed([]int{30, 11, 23, 4, 20}, 5) != 30      { panic("test 2") }
    if minEatingSpeed([]int{30, 11, 23, 4, 20}, 6) != 23      { panic("test 3") }
    if minEatingSpeed([]int{1}, 1) != 1                        { panic("test 4") } // single pile, exact fit
    if minEatingSpeed([]int{1000000000}, 2) != 500000000       { panic("test 5") } // large pile, 2 hours
    fmt.Println("all tests pass")
}

Related data structures

• Arrays, the piles array; feasibility predicate

Related concepts

• Binary Search on Answer, the feasibility search pattern for a monotonic yes or no condition.
• Binary Search, the halving tactic for ordered spaces where one side can be discarded.