Koko Eating Bananas

Medium

Problem

There are piles of bananas and h hours. Each hour Koko picks one pile and eats k bananas from it (or the whole pile if it has fewer). Return the minimum integer speed k that lets her finish every pile within h hours.

Example 1

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

Example 2

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

Test cases

Case 1

Input:    [3,6,7,11], 8
Expected: 4

Case 2

Input:    [30,11,23,4,20], 5
Expected: 30

Case 3

Input:    [30,11,23,4,20], 6
Expected: 23

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Binary search on the speed

Time O(n log max)Space O(1)

Hours needed falls as speed rises (monotonic). Find the smallest speed in [1, max pile] that finishes within h.

function minEatingSpeed(piles, h) {
let lo = 1, hi = Math.max(...piles);
while (lo < hi) {
const k = (lo + hi) >> 1;
let hours = 0;
for (const p of piles) hours += Math.ceil(p / k);
if (hours <= h) hi = k;
else lo = k + 1;
}
return lo;
}