mafeshsho8lmafeshsho8l
Get Started
All coding questions

Koko Eating Bananas

medium
NeetCode 150binary-searchgreedy

Problem

Given piles of bananas and a number of hours, find the smallest integer eating speed such that all piles are finished within the time. Each hour Koko eats from one pile up to her speed, finishing partial piles in that hour.

Examples

Input: piles = [3, 6, 7, 11], hours = 8
Output: 4
Speed 4 clears every pile within eight hours.
Input: piles = [30, 11, 23, 4, 20], hours = 5
Output: 30
Only the maximum speed fits five hours.

Constraints

  • • 1 <= piles.length <= 10^4
  • • piles.length <= hours <= 10^9
  • • 1 <= pile size <= 10^9
Hints(tap to reveal)
  • 1. The feasible speeds form a monotonic range.
  • 2. Binary search the answer over possible speeds.
Optimal approach(spoiler)
  1. The minimum speed is one and the maximum is the largest pile.
  2. Binary search over candidate speeds.
  3. For a speed, sum the ceiling of each pile divided by the speed as hours needed.
  4. Move toward smaller speeds while the time stays within the limit.
  5. O(n log max) time, O(1) space.

Ready to solve it?

Write your solution in the editor and get an instant AI grade on correctness, edge cases, and complexity.

Practice in the editor