Koko Eating Bananas

Binary search the minimum hourly eating speed Koko needs to finish all piles in h hours.

Medium
Time O(n log max) Space O(1)
LeetCode
3 min read
binary-search

Problem#

Koko eats k bananas per hour. For each pile, she keeps eating until it’s gone (no spillover within the hour). Return the minimum k such that she finishes all piles within h hours.

Examples#

  • piles = [3,6,7,11], h = 84
  • piles = [30,11,23,4,20], h = 530

Constraints#

  • 1 <= piles.length <= n <= h.

Approach#

Binary search on k in [1, max(piles)]. Feasibility: sum(ceil(p / k)) ≤ h.

Solution#

Koko Eating Bananas
class Solution {
public:
int minEatingSpeed(vector<int>& piles, int h) {
int lo = 1, hi = *max_element(piles.begin(), piles.end());
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
long long hours = 0;
for (int p : piles) hours += (p + mid - 1) / mid;
if (hours <= h) hi = mid;
else lo = mid + 1;
}
return lo;
}
};

Editorial#

Time-to-finish is monotonically non-increasing in k, so binary search converges to the smallest feasible k. ceil(p/k) = (p + k - 1) / k is the integer-arithmetic ceiling.

Complexity#

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

Concept revision#

Search ESC

Keyboard shortcuts

Shortcuts are disabled while typing in inputs.