Koko Eating Bananas medium

Koko Eating Bananas

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 eats k bananas. If the number of bananas in a pile is less than k, she will finish eating it in one hour. If the number of bananas in a pile is more than k, she will eat k bananas from that pile and continue eating the rest next hour. The goal is to find the minimum integer k such that she can eat all the bananas within h hours.

Example 1:

piles = [3,6,7,11], h = 8

Output: 4

Example 2:

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

Output: 30

Steps and Explanation:

The problem can be solved using binary search. The search space for k (eating speed) is from 1 (minimum speed to eat at least one banana per hour) to the maximum number of bananas in a single pile (maximum speed).

1. Find the search space: The minimum speed is 1, and the maximum speed is maxPile (the largest number of bananas in any pile).

2. Binary Search: We perform a binary search within this range. For each k (midpoint in the search space):

   • Calculate the total hours needed to eat all bananas with speed k.
   • If the total hours are less than or equal to h, it means we can potentially reduce the speed (k), so we search in the left half.
   • Otherwise, we need to increase the speed (k), so we search in the right half.

3. Calculate total hours: To calculate the total hours needed for a given k, we iterate through the piles array. For each pile, we calculate the number of hours needed to eat that pile using ceiling division ((piles[i] + k - 1) / k). We sum up the hours for all piles.

4. Return the result: The binary search will eventually converge to the minimum k that satisfies the condition.

Code (Java):

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int maxPile = 0;
        for (int pile : piles) {
            maxPile = Math.max(maxPile, pile);
        }

        int left = 1;
        int right = maxPile;
        int result = maxPile; // Initialize with the maximum possible value

        while (left <= right) {
            int k = left + (right - left) / 2; // Avoid integer overflow
            long totalHours = 0;
            for (int pile : piles) {
                totalHours += (pile + k - 1) / k; // Ceiling division
            }

            if (totalHours <= h) {
                result = k;
                right = k - 1; // Try a smaller speed
            } else {
                left = k + 1; // Need a faster speed
            }
        }

        return result;
    }
}

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 binary search takes log M steps, and calculating totalHours takes O(N) time in each step.
• Space Complexity: O(1). The algorithm uses a constant amount of extra space.