875. Koko Eating Bananas

Intuition

Koko wants to finish eating all the bananas within h hours. She eats from one pile per hour, and the speed k(bananas/hour) is the same for all hours. The faster she eats, the fewer hours she'll take.

The problem is to find the minimum possible eating speed k such that total time ≤ h. Since the relationship between speed and hours is monotonic (higher speed → fewer hours), we can apply binary search on k.

Complexity

Space Complexity	Time Complexity
$\text{O}(1)$	$\text{O}(\log{N})$

Code

// Helper function to calculate how many hours it takes to eat all bananas at speed 'eatingSpeed'
long hoursToFinish(int[] bananaPiles, long eatingSpeed) {
    long totalHours = 0;

    for (int pile : bananaPiles) {
        // Each pile takes ceil(pile / eatingSpeed) hours to eat
        totalHours += pile / eatingSpeed;
        if (pile % eatingSpeed != 0) totalHours++;
    }

    return totalHours;
}

public int minEatingSpeed(int[] bananaPiles, int allowedHours) {
    long minSpeed = 1;
    long maxSpeed = 1;
    long optimalSpeed = 0;

    // Find the maximum pile size to set upper limit for binary search
    for (int pile : bananaPiles) {
        maxSpeed = Math.max(maxSpeed, pile);
    }

    // Binary search on eating speed
    while (minSpeed <= maxSpeed) {
        long midSpeed = minSpeed + (maxSpeed - minSpeed) / 2;

        long requiredHours = hoursToFinish(bananaPiles, midSpeed);

        if (requiredHours <= allowedHours) {
            optimalSpeed = midSpeed;    // Try to find a slower (minimal) valid speed
            maxSpeed = midSpeed - 1;
        } else {
            minSpeed = midSpeed + 1;    // Too slow, increase speed
        }
    }

    return (int) optimalSpeed;
}