Koko Eating Bananas

Problem

Koko loves to eat bananas. There are n piles of bananas, the ith pile has piles[i] bananas. The guards have gone and will come back in h hours.

Koko can decide her bananas-per-hour eating 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 the guards return.

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

Example 3:

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

Constraints:

1 <= piles.length <= 10^4
piles.length <= h <= 10^9
1 <= piles[i] <= 10^9

Solution

Approach: Binary Search on Answer

The key insight is to binary search on the eating speed k rather than searching through the piles. We search for the minimum k in the range [1, max(piles)] that allows Koko to finish within h hours.

For a given speed k, we can calculate the total hours needed:

For each pile, hours = ceil(pile / k) = (pile + k - 1) // k

Algorithm:

Binary search on speed k in range [1, max(piles)]
For each mid speed, calculate total hours needed
If hours <= h, try smaller speed (search left)
If hours > h, need faster speed (search right)

Implementation

import math

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        def canFinish(k):
            # Calculate total hours needed with speed k
            hours = 0
            for pile in piles:
                hours += math.ceil(pile / k)
            return hours <= h

        left, right = 1, max(piles)
        result = right

        while left <= right:
            mid = (left + right) // 2

            if canFinish(mid):
                result = mid  # Valid speed, try to find smaller
                right = mid - 1
            else:
                left = mid + 1  # Too slow, need faster speed

        return result

Alternative (Without Math.ceil):

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        def hoursNeeded(k):
            hours = 0
            for pile in piles:
                # Ceiling division without math.ceil
                hours += (pile + k - 1) // k
            return hours

        left, right = 1, max(piles)

        while left < right:
            mid = (left + right) // 2

            if hoursNeeded(mid) <= h:
                right = mid  # Valid speed, try smaller
            else:
                left = mid + 1  # Too slow, need faster

        return left

Complexity Analysis

Time Complexity: O(n log m), where n is the number of piles and m is the maximum pile size. We do O(log m) binary search iterations, and each iteration requires O(n) to calculate hours.
Space Complexity: O(1), we only use a constant amount of extra space.

Key Insights

Binary Search on Answer: Instead of searching through array elements, we binary search on possible answer values (eating speed). This pattern applies when we can verify a candidate answer in reasonable time.
Monotonic Property: If Koko can finish with speed k, she can also finish with any speed greater than k. This monotonic property makes binary search applicable.
Ceiling Division: For pile size p and speed k, hours needed is ceil(p/k). We can compute this as (p + k - 1) // k without floating point operations.
Search Space Bounds: Minimum speed is 1 (eat one banana per hour). Maximum speed is max(piles) (eating the largest pile in one hour doesn’t help finish faster).
Feasibility Check: For each candidate speed, we check if it’s feasible (can finish in time). If yes, we try to minimize; if no, we must increase speed.