#875

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Koko Eating Bananas

Koko Eating Bananas challenges you to find the minimum eating speed to finish piles of bananas in a given time using binary search.

array binary search

Problem Statement

Koko has several piles of bananas, with each pile containing a certain number of bananas. Koko has a fixed number of hours, h, to eat all the bananas. The goal is to determine the minimum number of bananas, k, that Koko must eat per hour to finish all the bananas within h hours. If she can’t finish within h hours, the eating speed is too slow.

Each hour, Koko chooses a pile and eats as many bananas as her current speed, k, allows. If the pile contains fewer bananas than k, she finishes the pile. Your task is to calculate the minimum k using binary search over the valid answer space, ensuring Koko can eat all piles before the guards return.

Examples

Example 1

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

Output: 4

Example details omitted.

Example 2

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

Output: 30

Example details omitted.

Example 3

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

Output: 23

Example details omitted.

Constraints

1 <= piles.length <= 104
piles.length <= h <= 109
1 <= piles[i] <= 109

Solution Approach

Binary Search for Minimum Speed

The solution uses binary search over the possible eating speeds, with the lower bound starting from 1 banana per hour and the upper bound being the largest pile of bananas. At each step, we compute the total number of hours Koko would take to eat all bananas with the current speed. If the total time is less than or equal to h, the speed is valid, and we attempt a lower speed. Otherwise, we increase the speed.

Feasibility Check

For each candidate speed, a helper function calculates the number of hours required to finish all piles. For a given speed k, the function computes the total time Koko needs by summing up the hours for each pile. If the pile has fewer bananas than k, Koko eats all of them in one hour; otherwise, she takes one hour for each k bananas. This helps determine if the current speed is feasible.

Edge Case Considerations

Edge cases include situations where the number of piles is minimal or the total number of hours is large. The binary search method efficiently handles these cases by narrowing down the valid range of speeds, ensuring that the solution scales even with the upper constraint limits.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of the binary search approach is O(log(max(piles))) due to the binary search over the possible speeds, where max(piles) is the maximum number of bananas in a pile. For each speed, we calculate the total time needed in O(n), where n is the number of piles. Thus, the overall complexity is O(n log(max(piles))). The space complexity is O(1), since we only need a few variables for computation.

What Interviewers Usually Probe

The candidate demonstrates an understanding of binary search by efficiently narrowing down the valid range of speeds.
The candidate accurately implements a feasibility check for each candidate speed, ensuring that Koko finishes in time.
The candidate handles edge cases well, ensuring the solution works even for the largest inputs.

Common Pitfalls or Variants

Common pitfalls

Misunderstanding the binary search space: candidates may mistakenly define the range of speeds incorrectly, such as starting with the wrong lower or upper bound.
Incorrectly implementing the time calculation: the candidate may fail to correctly calculate how many hours Koko needs for each pile.
Not handling large input sizes efficiently: candidates may overlook the performance of their solution, resulting in an inefficient or slow approach.

Follow-up variants

Adjust the problem by changing the number of piles or the time limit to test the efficiency of the solution.
Consider variations where Koko can eat from multiple piles simultaneously, changing the problem’s complexity.
Increase the number of piles significantly to test how the binary search approach scales.

FAQ

How does binary search help in the Koko Eating Bananas problem?

Binary search efficiently narrows down the minimum speed by testing feasible speeds and narrowing the range based on the result of each test.

What is the time complexity of the Koko Eating Bananas problem?

The time complexity is O(n log(max(piles))), where n is the number of piles and max(piles) is the largest pile size.

What is the correct way to implement the time calculation for each candidate speed?

For each pile, calculate how many hours it takes to finish eating with the current speed, summing these hours across all piles.

What should I do if the solution takes too long for large inputs?

Ensure that the binary search space is set up correctly and consider optimizing the implementation of the feasibility check.

How does GhostInterview assist in solving this problem?

GhostInterview helps by guiding through binary search applications, highlighting common mistakes, and providing tailored practice for interview success.

terminal

Solution

Solution 1: Binary Search

We notice that if Koko can eat all the bananas at a speed of $k$ within $h$ hours, then she can also eat all the bananas at a speed of $k' > k$ within $h$ hours. This shows monotonicity, so we can use binary search to find the smallest $k$ that satisfies the condition.

1

2

3

4

5

6

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        def check(k: int) -> bool:
            return sum((x + k - 1) // k for x in piles) <= h

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

Continue Practicing

#862 shortest subarray with sum at least k #888 fair candy swap #852 peak index in a mountain array