Koko Eating Bananas medium

Problem Statement

Koko loves to eat bananas. There are piles of bananas, where piles[i] is the number of bananas in the i-th pile. Koko can decide her eating speed k. Each hour, she chooses some pile of bananas, and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour.

Koko likes to eat slowly, but still wants to finish eating all the bananas before h hours.

Return the minimum integer k such that she can eat all the bananas within h hours.

Example 1

Input: piles = [3,6,7,11], h = 8 Output: 4

Example 2

Input: piles = [30,11,23,4,20], h = 5 Output: 30

Steps

1. Define the search space: The minimum speed is 1 (eating one banana per hour) and the maximum speed is the largest pile size (eating all bananas in the largest pile in one hour).

2. Binary Search: We'll use binary search to efficiently find the minimum speed. The search space is bounded by 1 and max(piles).

3. Check Feasibility: For each potential speed k, we need to check if Koko can eat all bananas within h hours. We do this by iterating through each pile and calculating the time required to eat that pile at speed k. We sum up these times. If the total time is less than or equal to h, the speed k is feasible.

4. Adjust Search Space: Based on the feasibility check, we adjust the search space (left and right bounds) for the binary search.

5. Return Minimum Speed: The binary search continues until the left and right bounds converge. The final left bound will be the minimum speed.

Explanation

The problem is about finding the minimum speed to complete a task within a time constraint. A brute-force approach would be to test every possible speed from 1 to the maximum pile size, which is inefficient. Binary search is a much more efficient algorithm because it cuts the search space in half with each iteration. The feasibility check is crucial in determining whether a given speed is sufficient to meet the time constraint.

Code

function minEatingSpeed(piles: number[], h: number): number {
    let left = 1;
    let right = Math.max(...piles); // Maximum pile size

    while (left < right) {
        const mid = Math.floor((left + right) / 2); // Potential speed

        let hoursNeeded = 0;
        for (const pile of piles) {
            hoursNeeded += Math.ceil(pile / mid); // Time to eat current pile
        }

        if (hoursNeeded <= h) {
            right = mid; // Speed is feasible, try a lower speed
        } else {
            left = mid + 1; // Speed is too slow, try a higher speed
        }
    }

    return left; // Minimum feasible speed
}

Complexity

• Time Complexity: O(N log M), where N is the number of piles and M is the maximum number of bananas in a pile. The log M factor comes from the binary search.

• Space Complexity: O(1). The algorithm uses a constant amount of extra space.