Start learning free

LESSON 378 OF 671 · BINARY SEARCH

Koko Eating Bananas

Practice O(n log m)

You get an array of integers piles and an integer h. Pile i holds piles[i] bananas. Koko has h hours to eat all n piles.

Return the slowest whole-number speed k at which she finishes every pile within h hours.

At speed k, she eats up to k bananas each hour, from a single pile. If that pile has fewer left, she finishes it and waits for the next hour. So a pile of p bananas takes p / k hours, rounded up.

 

Example 1:

Input: piles = [5,9,2], h = 6
Output: 3
Explanation: At speed 3 the piles take 2 + 3 + 1 = 6 hours, just enough.
At speed 2 they would take 3 + 5 + 1 = 9 hours.

Example 2:

Input: piles = [8,15,4], h = 3
Output: 15
Explanation: 3 piles in 3 hours means one hour per pile.
The biggest pile has 15 bananas, so the speed must be 15.

Example 3:

Input: piles = [12], h = 5
Output: 3
Explanation: At speed 3 the only pile takes 4 hours, within the 5.
At speed 2 it would take 6.

 

Constraints:

  • 1 to 10,000 piles.
  • Each pile has 1 to 109 bananas.
  • h is at least the number of piles and at most 109.

Note:

Your algorithm should run in O(n log m) time, where m is the biggest pile, and use O(1) extra space.

At a slow speed, the hours add up fast. At speed 1, 104 piles of 109 bananas take 1013 hours. That is far more than a 32-bit integer can hold.

STEP 1 OF 13
    Ctrl + Enter to check