875. Koko Eating Bananas

Description

In this problem, we need to determine the minimum eating speed that allows a person to finish eating all the piles of bananas within a given number of hours. The input consists of an array representing the piles of bananas and an integer h representing the maximum hours available. The challenge is to find the minimum speed k such that the person can eat all the bananas in h hours or less.

Intuition

The problem involves finding the smallest possible value of k that satisfies the condition. A brute-force approach would test every possible value of k, but this would be inefficient. Instead, we can use binary search to efficiently narrow down the possible values of k. The binary search will allow us to find the minimum speed by repeatedly halving the search range until the optimal value is found.

Approach

1. Initialize the Search Space: Set the initial values for low as 1 (the minimum speed) and high as the maximum value in the piles array (the maximum speed).
2. Binary Search: Perform binary search on the speed k. - Calculate mid as the average of low and high. - Check if it's possible to eat all bananas within h hours using speed k = mid. - If yes, this means we might be able to find a smaller speed, so we adjust the high value to mid - 1. - If no, this means the speed is too slow, so we adjust the low value to mid + 1.
3. Check Function: A helper function checks if a given speed k can finish all the piles within h hours by iterating through the piles array and calculating the total hours required.
4. Return the Result: Once the binary search completes, low will contain the minimum eating speed required.

Complexity

Time Complexity:

O(n log m), where n is the number of piles and m is the range of possible speeds (from 1 to the maximum number of bananas in a pile). The binary search runs in O(log m), and for each iteration, we check if the speed is valid in O(n).

Space Complexity:

O(1) since we only use a few extra variables and no additional data structures.

Code

C++

class Solution {
public:
    int minEatingSpeed(vector& piles, int h) {
        int l = 1;
        int high = *max_element(piles.begin(), piles.end());
        int ans = high;  // Initialize ans with the maximum possible value

        while (l <= high) {
            int mid = l + (high - l) / 2;
            if (canEatAll(piles, h, mid)) {
                ans = mid;
                high = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return ans;
    }

private:
    bool canEatAll(const vector& piles, int h, int k) {
        long long hours = 0;  // Use long long to store the number of hours

        for (int pile : piles) {
            hours += (pile + k - 1) / k;  // This is equivalent to ceil(pile / k)
            if (hours > h) {
                return false;
            }
        }
        return true;
    }
};

Python

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        l = 1
        high = max(piles)
        ans = -1

        def checkHrs(mid, piles):
            hrs = 0
            for pile in piles:
                hrs += (pile + mid - 1) // mid  # Equivalent to ceil(pile / mid)
            return hrs

        while l <= high:
            mid = (l + high) // 2
            hrs = checkHrs(mid, piles)

            if hrs <= h:
                ans = mid
                high = mid - 1
            else:
                l = mid + 1
        
        return ans

Java

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int l = 1;
        int high = Integer.MIN_VALUE;
        for (int pile : piles) {
            high = Math.max(high, pile);
        }
        int ans = high;

        while (l <= high) {
            int mid = l + (high - l) / 2;
            if (canEatAllInTime(piles, h, mid)) {
                ans = mid;
                high = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return ans;
    }

    private boolean canEatAllInTime(int[] piles, int h, int k) {
        int hrs = 0;
        for (int pile : piles) {
            // Using (pile + k - 1) / k is equivalent to ceil(pile / k) and prevents overflow
            hrs += (pile + k - 1) / k;
            if (hrs > h) {
                return false;  // Early exit if we already exceed hours
            }
        }
        return hrs <= h;
    }
}

JavaScript

var minEatingSpeed = function (piles, h) {
    let l = 1
    let high = Math.max(...piles)
    let ans = -1
    function checkHrs(mid, piles) {
        let hrs = 0
        console.log(mid)
        for (let i = 0; i < piles.length; i++) {
            hrs += Math.ceil(piles[i] / mid)
        }
        console.log(hrs, 'hrs')
        return hrs
    }

    while (l <= high) {
        let mid = Math.floor((l + high) / 2)

        const hrs = checkHrs(mid, piles)

        if (hrs <= h) {
            ans = mid
            high = mid - 1
        }
        else l = mid + 1
    }
    return ans
};