šŸ”— LeetCodešŸ”— Neetcode

Koko Eating Bananas

Mediumbinary searchGoogleAmazonMeta

Koko loves to eat bananas. There are n piles of bananas, the ith pile has piles[i] bananas. The guards have gone and will come back in h hours.


Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses a pile and eats k bananas from it. If the pile has less than k bananas, she eats all of them and won't eat any more during that hour.


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

Examples

Input:piles = [3,6,7,11], h = 8
Output:4
Input:piles = [30,11,23,4,20], h = 5
Output:30
Input:piles = [30,11,23,4,20], h = 6
Output:23

Constraints

  • 1 <= piles.length <= 10^4
  • piles.length <= h <= 10^9
  • 1 <= piles[i] <= 10^9

šŸ’” Hints

Hint 1

Binary search on the answer: the eating speed k.

Hint 2

The search range is [1, max(piles)].

Hint 3

For each candidate k, calculate total hours needed. If hours <= h, try smaller k.

Algorithm Complexity

Official asymptotic Big-O runtime and auxiliary memory analysis

Linearithmic
Algorithmic Approach

Binary search on the eating speed. For each candidate speed, calculate total hours. If feasible (<= h), try smaller. Otherwise, try larger.

Time ComplexityO(n * log(max(piles)))
Why:

Binary search over the speed range [1, max(piles)] takes O(log(max(piles))) iterations, each running an O(n) feasibility check.

Space ComplexityO(1)
Why:

Feasibility check and binary search use constant O(1) auxiliary variables.

Big-O Growth CurveLinearithmic (O(N log N))
Scales efficiently for sorting and divide-and-conquer algorithms.

šŸŒ Real-World Use Cases

Cloud ComputingResource allocation

Finding the minimum server throughput (processing speed) needed to complete all tasks within a deadline ā€” binary search on the answer.

šŸ” Dry Run

Solutionā± O(n * log(max(piles))) | šŸ’¾ O(1)
Line2
left=1number
right=11number
h=8number

Input: piles=[3,6,7,11], h=8. Binary search speed in [1..11].