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 bananas-per-hour speed of 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

Explanation: Koko can eat all the bananas in 8 hours if her speed is 4:

• Hour 1: Eat 4 bananas from the first pile (3 + 1)
• Hour 2: Eat 4 bananas from the second pile (6)
• Hour 3: Eat 4 bananas from the third pile (7)
• Hour 4: Eat 4 bananas from the fourth pile (11) If her speed is less than 4, she will need more than 8 hours.

Example 2:

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

Explanation: Koko can eat all the bananas in 5 hours if her speed is 30. She can eat 30 bananas from the first pile in the first hour, etc.

Steps:

1. Define a function minEatingSpeed: This function takes the piles array and h as input.
2. Binary Search: The key is to realize that the minimum speed is 1 (eat one banana per hour) and the maximum speed is the largest pile size (eat all bananas in a pile in one hour). We can use binary search to efficiently find the minimum speed within this range.
3. Check Feasibility: In each iteration of the binary search, we calculate the total hours needed with the current speed k. We do this by iterating through the piles and calculating the ceiling of piles[i] / k (number of hours needed for each pile). If the total hours exceed h, we need a faster speed (increase the left bound of the search). Otherwise, we try a slower speed (decrease the right bound).
4. Return the minimum speed: The loop continues until left becomes equal to right, at which point left (or right) represents the minimum speed.

Explanation:

Binary search is used because the time required to eat all bananas is a monotonically decreasing function of the eating speed. If a speed k takes too long, then any speed less than k will also take too long. Conversely, if a speed k is fast enough, then any speed greater than k will also be fast enough. This monotonic property makes binary search an efficient approach.

Code:

import math

def minEatingSpeed(piles, h):
    left, right = 1, max(piles)  # Initialize the search space
    while left < right:
        mid = (left + right) // 2
        total_hours = sum(math.ceil(pile / mid) for pile in piles)
        if total_hours <= h:
            right = mid  # Try a slower speed
        else:
            left = mid + 1  # Need a faster speed
    return left  # left == right at the end

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 iterating through the N piles.
• Space Complexity: O(1). The algorithm uses a constant amount of extra space.