Koko Eating Bananas

Medium Problem 44 of 151 Java and Python

Problem

There are n piles of bananas; pile i has piles[i] bananas. Koko eats at a speed of k bananas per hour. Each hour she picks one pile and eats k bananas from it; if it has fewer than k, she finishes it and waits for the rest of the hour.

Return the minimum integer k that lets her eat all the bananas within h hours.

Example 1

Input: piles = [3, 6, 7, 11], h = 8
Output: 4
Why: At speed 4 she needs 1 + 2 + 2 + 3 = 8 hours.

Example 2

Input: piles = [30, 11, 23, 4, 20], h = 5
Output: 30
Why: One pile per hour, so she must finish the biggest pile in an hour.

Constraints

1 ≤ piles.length ≤ 10⁴
piles.length ≤ h ≤ 10⁹
1 ≤ piles[i] ≤ 10⁹

Explanation

The hours needed at speed k are sum(ceil(pile / k)). A faster speed never takes longer, so the answers look like: too slow, too slow, …, fast enough, fast enough.

That monotonic yes/no pattern is what binary search needs. Search the speed between 1 and the largest pile for the first speed that is fast enough.

Approach 1 · Naive

Try every speed

Time O(n · max(piles))
Space O(1)

Start at speed 1 and increase until the total hours fit within h.

For k = 1, 2, …, compute the hours needed.
Return the first k with hours ≤ h.

Java

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        for (int k = 1; ; k++) {
            long hours = 0;
            for (int pile : piles) {
                hours += (pile + k - 1) / k;
            }
            if (hours <= h) {
                return k;
            }
        }
    }
}

Python

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        k = 1
        while True:
            hours = sum((pile + k - 1) // k for pile in piles)
            if hours <= h:
                return k
            k += 1

Approach 2 · Optimal

Binary search on the speed

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

Binary-search k in [1, max(piles)] for the smallest speed whose total hours fit.

Set lo = 1, hi = max(piles).
While lo < hi: if hours(mid) <= h, hi = mid (it works, maybe slower works too); else lo = mid + 1.
Return lo.

Java

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int lo = 1;
        int hi = 0;
        for (int pile : piles) {
            hi = Math.max(hi, pile);
        }
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            long hours = 0;
            for (int pile : piles) {
                hours += (pile + mid - 1) / mid;
            }
            if (hours <= h) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }
}

Python

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        lo, hi = 1, max(piles)
        while lo < hi:
            mid = (lo + hi) // 2
            hours = sum((pile + mid - 1) // mid for pile in piles)
            if hours <= h:
                hi = mid
            else:
                lo = mid + 1
        return lo

Complexity compared

Approach	Time	Space
Naive Try every speed	O(n · max(piles))	O(1)
Optimal Binary search on the speed	O(n · log max(piles))	O(1)

Key takeaways

"Binary search on the answer": when you can check a guess quickly and checks are monotonic, search over the guesses.
(pile + k - 1) / k is integer ceiling division; use a long sum in Java, since hours can exceed 2³¹.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem