875. Koko Eating Bananas

At a Glance

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

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.

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

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

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;
}