Problem Description

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.

Intuition

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.

Learn more about Binary Search patterns.

Solution Approach

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:

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 uses Python's bisect_left function in an elegant way:

return 1 + bisect_left(range(1, max(piles) + 1), True, key=check)

This works because:

• bisect_left searches for the leftmost position where True can be inserted in a sorted sequence
• The key=check parameter transforms each speed value into a boolean (can Koko finish in time?)
• For speeds too slow, check returns False; for speeds fast enough, it returns True
• Since we want speeds that work (True values), and False < True in Python, the sequence looks like: [False, False, ..., False, True, True, ..., True]
• bisect_left finds the first True position, which corresponds to the minimum valid speed
• Adding 1 adjusts for the 0-based indexing of bisect_left on the range starting from 1

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

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Example: piles = [3, 6, 7, 11], h = 8

Step 1: Initialize binary search boundaries

• Left boundary: l = 1 (minimum eating speed)
• Right boundary: r = max([3, 6, 7, 11]) = 11 (maximum useful speed)
• Search range: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

Step 2: Apply binary search with the check function

The check(k) function calculates if speed k allows finishing within 8 hours:

• For each pile, we calculate hours needed using (pile + k - 1) // k

Let's evaluate check for different speeds:

• k = 1: Hours needed = (3+0)//1 + (6+0)//1 + (7+0)//1 + (11+0)//1 = 3 + 6 + 7 + 11 = 27 → 27 > 8 → False
• k = 2: Hours needed = (3+1)//2 + (6+1)//2 + (7+1)//2 + (11+1)//2 = 2 + 4 + 4 + 6 = 16 → 16 > 8 → False
• k = 3: Hours needed = (3+2)//3 + (6+2)//3 + (7+2)//3 + (11+2)//3 = 1 + 3 + 3 + 5 = 12 → 12 > 8 → False
• k = 4: Hours needed = (3+3)//4 + (6+3)//4 + (7+3)//4 + (11+3)//4 = 1 + 2 + 2 + 3 = 8 → 8 ≤ 8 → True
• k = 5: Hours needed = (3+4)//5 + (6+4)//5 + (7+4)//5 + (11+4)//5 = 1 + 2 + 2 + 3 = 8 → 8 ≤ 8 → True

The sequence of check results looks like:

Speed:  [1,     2,     3,     4,    5,    6,    7,    8,    9,    10,   11]
Result: [False, False, False, True, True, True, True, True, True, True, True]

Step 3: Find the minimum valid speed

Using bisect_left:

• We search for the leftmost position where True can be inserted
• The first True appears at index 3 (corresponding to speed 4)
• Since we're searching in range(1, 12), we add 1 to convert from 0-based index to actual speed
• Result: 1 + 3 = 4

Verification for k = 4:

• Pile 1 (3 bananas): needs ⌈3/4⌉ = 1 hour
• Pile 2 (6 bananas): needs ⌈6/4⌉ = 2 hours
• Pile 3 (7 bananas): needs ⌈7/4⌉ = 2 hours
• Pile 4 (11 bananas): needs ⌈11/4⌉ = 3 hours
• Total: 1 + 2 + 2 + 3 = 8 hours ✓

The minimum eating speed is 4 bananas per hour.

Solution Implementation

Time and Space Complexity

The time complexity is O(n × log M), where n is the length of the array piles and M is the maximum value in piles. This is because:

• The binary search using bisect_left searches through the range [1, max(piles)], which has M elements, taking O(log M) iterations
• For each iteration of the binary search, the check function is called, which computes the sum of (x + k - 1) // k for all elements in piles, taking O(n) time
• Therefore, the total time complexity is O(n × log M)

The space complexity is O(1). The algorithm only uses a constant amount of extra space for:

• The variable k in the check function
• The internal variables used by bisect_left
• The generator expression in the sum function doesn't create a list but computes values on-the-fly

Note that while range(1, max(piles) + 1) is passed to bisect_left, the implementation of bisect_left with a key function doesn't materialize the entire range into memory but treats it as virtual bounds for the binary search.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Binary Search Boundaries

A common mistake is setting the right boundary as sum(piles) or sum(piles) // h instead of max(piles). While these might seem logical, they're inefficient and can cause issues:

Why it's wrong:

• If k > max(piles), Koko still takes 1 hour per pile (she can't eat faster than the pile size)
• Setting r = sum(piles) creates an unnecessarily large search space
• Using sum(piles) // h might be too small if piles are unevenly distributed

Correct approach:

# Right boundary should be max(piles)
left, right = 1, max(piles)

2. Incorrect Ceiling Division

Many developers incorrectly calculate the hours needed for each pile:

Common mistakes:

# Wrong: Simple division truncates, underestimating hours needed
hours = pile // k  # This would give 2 for pile=7, k=3 (should be 3)

# Wrong: Using math.ceil without importing
hours = ceil(pile / k)  # NameError if math not imported

# Wrong: Float division issues
hours = int(pile / k) + (1 if pile % k > 0 else 0)  # Verbose and error-prone

Correct approach:

# Efficient ceiling division without imports
hours = (pile + k - 1) // k
# Or alternatively:
hours = -(-pile // k)  # Using negative division trick

3. Off-by-One Error in Binary Search

When implementing manual binary search, it's easy to get the boundaries wrong:

Common mistake:

def minEatingSpeed(self, piles: List[int], h: int) -> int:
    left, right = 1, max(piles)
  
    while left < right:  # Wrong: might miss the answer
        mid = (left + right) // 2
        if can_finish(mid):
            right = mid - 1  # Wrong: might skip the minimum valid speed
        else:
            left = mid + 1
  
    return left  # Might return invalid speed

Correct approach:

def minEatingSpeed(self, piles: List[int], h: int) -> int:
    left, right = 1, max(piles)
  
    while left < right:
        mid = (left + right) // 2
        if can_finish(mid):
            right = mid  # Keep mid as potential answer
        else:
            left = mid + 1
  
    return left

4. Integer Overflow in Other Languages

While not an issue in Python, developers coming from other languages might worry about overflow:

Potential issue in languages like Java/C++:

# This could overflow in other languages
mid = (left + right) // 2

Safe approach (habit from other languages):

mid = left + (right - left) // 2

5. Misunderstanding the bisect_left Usage

The clever use of bisect_left with a boolean key can be confusing:

Common confusion:

# Wrong: Forgetting to add 1 to the result
return bisect_left(range(1, max(piles) + 1), True, key=check)  # Off by 1

# Wrong: Using bisect_right instead
return bisect_right(range(1, max(piles) + 1), True, key=check)  # Wrong boundary

Why the +1 is needed:

• bisect_left returns the index in the range where True would be inserted
• Since our range starts at 1 (not 0), we need to add 1 to get the actual speed value
• The range [1, 2, 3, ..., max(piles)] has indices [0, 1, 2, ..., max(piles)-1]