Koko Eating Bananas medium

Problem Statement

Koko loves to eat bananas. There are piles of bananas, and the i-th pile has piles[i] bananas. The guards have given Koko h hours to eat all bananas.

Koko can eat k bananas per hour. The rate k must be a positive integer. Each hour, Koko will eat k bananas from a pile. If the pile has less than k bananas, Koko will eat all of them instead, and will continue to the next pile.

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 to Solve

1. Binary Search: The problem can be solved efficiently using binary search. The search space is the range of possible eating rates k. The minimum rate is 1 (eating one banana per hour) and the maximum rate is the largest pile size (eating all bananas in a pile in one hour).

2. Check Feasibility: For a given rate k, we need a function to check if Koko can eat all bananas within h hours. This involves iterating through the piles and calculating the time required to eat each pile at rate k. The total time should not exceed h.

3. Binary Search Iteration: The binary search iteratively narrows down the search space. If a rate k is feasible (total time <= h), we try a smaller rate; otherwise, we try a larger rate.

4. Return Minimum Rate: The binary search continues until the minimum feasible rate is found.

Explanation

The key insight is that the time taken to eat bananas is a monotonically decreasing function of the eating rate k. This allows us to use binary search to find the minimum k. If a rate k allows Koko to finish within h hours, then any rate greater than k will also work. If a rate k is not sufficient, then any rate smaller than k will also not be sufficient.

The check function efficiently calculates the total time needed for a given rate. The binary search elegantly finds the minimum feasible rate by repeatedly halving the search space.

Code (C#)

public class Solution {
    public int MinEatingSpeed(int[] piles, int h) {
        int left = 1;
        int right = piles.Max(); // Maximum possible eating speed

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (check(piles, mid, h)) {
                right = mid; // Try a smaller rate
            } else {
                left = mid + 1; // Try a larger rate
            }
        }
        return left; // left will be the minimum feasible rate
    }

    private bool check(int[] piles, int k, int h) {
        long totalTime = 0;
        foreach (int pile in piles) {
            totalTime += (long)Math.Ceiling((double)pile / k); // Time to eat current pile
        }
        return totalTime <= h;
    }
}

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 O(log M) iterations, and each iteration involves checking all piles (O(N)).

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