875. Koko Eating Bananas

Quick Identifier

Topic: binary-search
Pattern: Binary Search (Search on answer)
Difficulty: Medium
Companies: Amazon, Google, Meta, DoorDash, Roblox
Frequency: High
LeetCode: 875

Quick Sights

Time Complexity: O(n log max) from the optimal approach.
Space Complexity: O(1) from the optimal approach.
Core Mechanism: Given pile sizes and a limit on hours hours, choose an integer eating speed (bananas per hour) so that all piles are finished within hours; each pile takes ceil(pile / speed) hours. Return the minimum feasible speed.

Given pile sizes and a limit on hours hours, choose an integer eating speed (bananas per hour) so that all piles are finished within hours; each pile takes ceil(pile / speed) hours. Return the minimum feasible speed.

The key is to state the invariant before coding: what part of the input is already settled, what state is still unresolved, and what single operation makes progress without losing correctness.

Recognition cues:

“Minimum maximum” or “smallest X such that predicate holds”
Monotonicity: if speed speed works, any speed+1 also works
ceil sum of per-pile times

Study Pattern (SDE3+)

0-3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

This diagram shows the algorithm movement for this problem family.

Loading diagram…

Approaches

Brute force — O(max * n) time / O(1) space — try every speed from 1 to max(piles).
Better — same monotonicity; still need to find transition point fast.
Optimal — O(n log max) time / O(1) space — binary search speed in [1, max]; check feasibility with sum of ceilings.

Optimal Solution

Go

func minEatingSpeed(piles []int, hours int) int {
	maxBananas := 0
	for _, pile := range piles {
		if pile > maxBananas {
			maxBananas = pile
		}
	}
	left, right := 1, maxBananas
	for left < right {
		mid := left + (right-left)/2
		if hoursNeeded(piles, mid) <= hours {
			right = mid
		} else {
			left = mid + 1
		}
	}
	return left
}

func hoursNeeded(piles []int, speed int) int {
	total := 0
	for _, pile := range piles {
		total += (pile + speed - 1) / speed
	}
	return total
}

JavaScript

function minEatingSpeed(piles, hours) {
	let maxBananas = 0;
	for (const pile of piles) {
		maxBananas = Math.max(maxBananas, pile);
	}
	let left = 1;
	let right = maxBananas;
	while (left < right) {
		const mid = left + Math.floor((right - left) / 2);
		if (hoursNeeded(piles, mid) <= hours) {
			right = mid;
		} else {
			left = mid + 1;
		}
	}
	return left;
}

function hoursNeeded(piles, speed) {
	let total = 0;
	for (const pile of piles) {
		total += Math.ceil(pile / speed);
	}
	return total;
}