Problem Breakdown
We are given an array of banana piles where each pile has a specific number of bananas (piles[i]). Koko needs to eat all these bananas within h hours before the guards return. She chooses a constant eating speed k. In one hour, she eats up to k bananas from one chosen pile. If a pile is smaller than k, she finishes it and stops for that hour (wasting remaining time).
Inputs:
piles: List of integers representing banana counts per pile ().h: Total hours available (, where ).
Output:
- Minimum integer speed
kto finish all bananas withinh.
Implicit Constraints & Edge Cases:
- Monotonicity: If a specific speed
kworks, any speed greater thankwill also work (finish time decreases or stays same as speed increases). This is the critical property for Binary Search. - Search Space Lower Bound: Speed must be at least 1 (
low = 1). - Search Space Upper Bound: We never need to eat faster than the largest pile in a single hour, because that guarantees every pile finishes within exactly one hour (total time ). Since
h >= N, this is always feasible. Thus,high = max(piles). - Feasibility Check: For any speed
k, total hours required is . We must ensure this sum does not exceedh.
Intuition
A naive brute force approach would be to iterate through every possible integer value of k starting from 1 up to the maximum pile size. For each k, we calculate if it’s feasible within h hours. However, since piles can have values up to , iterating linearly is too slow ().
The key insight lies in recognizing that feasibility is monotonic with respect to speed:
- If Koko eats at speed
k, she finishes within time. - Increasing her speed will only reduce or keep the same total hours needed; it never increases them.
- Decreasing her speed below a working threshold might cause her to exceed
h.
This allows us to use Binary Search on the Answer (the value of k). We search for the smallest valid k in the range . This reduces our complexity significantly.
Approach
- Initialize binary search bounds:
left = 1,right = max(piles). - While
left <= right:- Calculate
mid = (left + right) // 2as the candidate speed. - Check if this speed is feasible within
hhours using a helper calculation or inline logic: sum of(pile + mid - 1) // midfor all piles. This formula computes efficiently without floating point errors.
- Calculate
- If the total time required with
midspeed is less than or equal toh:- Record
midas a potential answer (ans = mid). - Try finding a slower valid speed by moving right bound:
right = mid - 1.
- Record
- If the total time exceeds
h:- The current speed is too slow; we need to eat faster. Move left bound up:
left = mid + 1.
- The current speed is too slow; we need to eat faster. Move left bound up:
- Return the recorded answer (
ans).
Complexity Analysis
- Time Complexity: . We perform a binary search over the range of possible speeds (up to iterations for max value ). Inside each iteration, we iterate through all piles () to calculate total hours. With , this is roughly operations, well within time limits.
- Space Complexity: auxiliary space (excluding input storage). We only use a few integer variables for the search bounds and counters.
Solution
import math
def minEatingSpeed(piles: list[int], h: int) -> int:
# Binary Search on Answer Space
left, right = 1, max(piles)
while left <= right:
k = (left + right) // 2
# Calculate total hours needed for speed k
# Using integer arithmetic to avoid float precision issues: ceil(a/b) -> (a + b - 1) // b
time_needed = sum((pile + k - 1) // k for pile in piles)
if time_needed <= h:
ans = k # Found a valid speed, try smaller one to minimize k
right = k - 1
else:
left = k + 1 # Not fast enough
return left
# Example usage matching LeetCode signature logic (returning the found min)
Edge Cases Handled
- Single Pile: The binary search correctly handles cases where
len(piles)is 1. If there’s only one pile, Koko just needs to eat it withinhhours; speed will be . - Large Values ( up to ): Python handles large integers automatically without overflow issues. The ceiling division formula
(pile + k - 1) // kensures precision is maintained using integer arithmetic rather than floating pointmath.ceil. - Minimum Time Constraint: Since the problem guarantees a solution exists (and specifically that ), we don’t need to handle impossible cases where even infinite speed cannot finish in time. The upper bound of binary search ensures we find the minimum valid integer within feasible bounds.