Koko has n piles of bananas in front of her, where the i-th pile contains piles[i] bananas. She needs to eat all the bananas before the guards return in h hours.

Koko eats bananas at a constant speed of k bananas per hour. During each hour, she follows these rules:

• She picks one pile to eat from
• If the pile has k or more bananas, she eats exactly k bananas from it
• If the pile has fewer than k bananas, she eats all remaining bananas in that pile and doesn't eat any more bananas during that hour (even if there's time left)

The goal is to find the minimum eating speed k (bananas per hour) that allows Koko to finish all bananas within h hours.

For example, if piles = [3, 6, 7, 11] and h = 8:

• If k = 4, Koko needs: 1 hour for pile 1 (3 bananas), 2 hours for pile 2 (6 bananas), 2 hours for pile 3 (7 bananas), and 3 hours for pile 4 (11 bananas), totaling 8 hours
• If k = 3, she would need 10 hours total, which exceeds the limit

The problem uses binary search because eating speeds have a monotonic property: if Koko can finish at speed k, she can also finish at any speed greater than k. The solution searches for the minimum valid speed between 1 and max(piles) using the helper function check(k) which calculates whether all bananas can be eaten within h hours at speed k. The expression (x + k - 1) // k computes the ceiling division to determine hours needed for each pile.

The key insight is recognizing that this problem has a monotonic property: if Koko can eat all bananas at speed k within h hours, then she can definitely eat them at any speed faster than k. Conversely, if she cannot finish at speed k, then she cannot finish at any speed slower than k either.

This monotonic behavior immediately suggests binary search as a solution strategy. We need to find the minimum value of k that satisfies our constraint - a classic "find the leftmost valid value" binary search problem.

The search space for k is bounded. The minimum possible speed is 1 (eating one banana per hour), and the maximum useful speed is max(piles) - eating any faster than the largest pile size provides no benefit since Koko can only eat from one pile per hour anyway.

For any given speed k, we can calculate how many hours Koko needs to finish all piles. For a pile with x bananas:

• If x is divisible by k, she needs exactly x / k hours
• If not, she needs x // k + 1 hours (the ceiling of x / k)

The formula (x + k - 1) // k elegantly computes the ceiling division without using floating-point arithmetic. This is equivalent to math.ceil(x / k) but avoids potential precision issues.

By using binary search on the range [1, max(piles)] and checking if each candidate speed allows Koko to finish within h hours, we can efficiently find the minimum valid speed in O(n * log(max(piles))) time, where n is the number of piles.

Pattern Learn more about Binary Search patterns.

Watch it run

Step through it below. Binary search finds the slowest eating speed whose total hours still fit within h.

The solution implements binary search to find the minimum eating speed. Here's how the algorithm works:

1. Set up the binary search boundaries:

• Left boundary l = 1 (minimum possible eating speed)
• Right boundary r = max(piles) (maximum useful eating speed)

2. Define the check function: The helper function check(k) determines if Koko can finish all bananas at speed k within h hours:

Copy
def check(k: int) -> bool:
    return sum((x + k - 1) // k for x in piles) <= h

• For each pile x, calculate hours needed: (x + k - 1) // k (ceiling division)
• Sum all hours needed across all piles
• Return True if total hours ≤ h, otherwise False

3. Apply binary search: The code searches for the first speed where check (named feasible in the code) returns True:

Copy
left, right = 1, max(piles)
first_true_index = -1
while left <= right:
    mid = (left + right) // 2
    if feasible(mid):
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1
return first_true_index

This works because:

• Over the speeds 1, 2, ..., max(piles), the results of feasible look like [False, False, ..., False, True, True, ..., True]
• When mid is feasible, it is a candidate answer, so the code records it in first_true_index and continues searching the smaller speeds with right = mid - 1
• When mid is not feasible, every smaller speed is also too slow, so the search moves to left = mid + 1
• When the loop ends, first_true_index holds the smallest feasible speed. Speed max(piles) is always feasible because h >= len(piles), so the answer is always found

Time Complexity: O(n * log(max(piles))) where n is the number of piles

• Binary search runs in O(log(max(piles))) iterations
• Each iteration calls check, which takes O(n) time to sum over all piles

Space Complexity: O(1) - only using constant extra space for variables