Back to DSA

Koko Eating Bananas

medium
Acceptance: 49%
Binary Search

There are n piles of fruit, with pile i containing piles[i] pieces. You can consume at most k pieces per hour from a single pile; if a pile has fewer than k pieces, you finish it in that hour and wait. Given h hours in total, find the smallest value of k that lets you finish all piles in time.

Examples

Example 1:
Input:piles = [5,8,12,6], h = 10
Output:5
Explanation: At speed 5: ceil(5/5)+ceil(8/5)+ceil(12/5)+ceil(6/5) = 1+2+3+2 = 8 hours, which fits within 10.
Example 2:
Input:piles = [20,10,15], h = 3
Output:20
Explanation: At speed 20, each pile takes exactly 1 hour, totaling 3 hours.

Hints

Related Problems

Longest Increasing SubsequencemediumSearch in Rotated Sorted ArraymediumFind Peak ElementmediumSplit Array Largest SumhardFind Minimum in Rotated Sorted Arraymedium
00:00
class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int lo = 1, hi = 0;
        for (int p : piles) hi = Math.max(hi, p);
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            int hours = 0;
            for (int p : piles) hours += (p + mid - 1) / mid;
            if (hours <= h) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }
}
Time complexityO(n * log(max(piles)))
Space complexityO(1)