875. Koko Eating Bananas - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

Koko loves eating bananas. There are n piles of bananas, where the i-th pile has piles[i] bananas. The guards have gone for h hours, and Koko can decide her eating speed k (bananas per hour). Each hour, she chooses a pile and eats up to k bananas from that pile. If she finishes a pile, she moves to the next one.

Koko wants to eat all the bananas within h hours. Find the minimum integer k such that she can finish all the bananas in time.

Examples

Example 1

Input:

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

Output:

Explanation: If Koko eats at a rate of 4 bananas per hour, she will finish all the piles in exactly 8 hours.

Example 2

Input:

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

Output:

Explanation: She must eat at a rate of 30 bananas per hour to finish all the bananas in 5 hours.

Example 3

Input:

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

Output:

Explanation: With 6 hours available, Koko can eat at a rate of 23 bananas per hour and finish all piles in time.

Constraints

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

Hints to Solve the Problem

Brute Force Approach: Try all possible eating speeds from 1 up to the size of the largest pile. Check if Koko can finish within h hours at that speed.
Optimized Approach: Use binary search to efficiently find the minimum valid k instead of checking every possible speed.
Key Observation: A slower eating speed means taking longer, and a faster speed means finishing sooner. This monotonic relationship suggests that binary search could be applied.

Approach 1: Brute Force (Try All Speeds)

Explanation

Iterate over possible speeds k from 1 to max(piles) (the size of the largest pile).
For each speed k, calculate the total time required by summing up ceil(pile / k) for each pile.
If the total hours needed is <= h, then Koko can finish with speed k. Return this k as soon as you find the first that works (which will be the minimum possible).
If none of the speeds up to max(piles) work (which shouldn't happen given the problem constraints), return -1.

Python Code

Python3

. . . .

Complexity Analysis

Time Complexity: O(N * M), where N is the number of piles and M is the size of the largest pile. In the worst case, this could be up to 10^9 * 10^4, which is not feasible. This brute force approach will time out for large inputs.
Space Complexity: O(1), since we only use a few extra variables for counting time.

Approach 2: Optimized Binary Search

Explanation

We can use binary search on the range of possible eating speeds (from 1 to max(piles)).
Set low = 1 and high = max(piles). While low < high:
- Choose mid = (low + high) // 2 as a candidate speed.
- Compute the total hours required at speed mid by summing ceil(pile / mid) for each pile.
- If the total hours <= h, then mid is fast enough (or even faster than necessary). Try a smaller speed by setting high = mid.
- If the total hours > h, then mid is too slow, so we must increase the speed. Set low = mid + 1.
When the loop ends, low (which is equal to high) will be the smallest speed that allowed finishing within h hours.

Python Code

Python3

. . . .

Java Code (Binary Search Approach)

Java

. . . .

Note: In the Java code above, (pile + mid - 1) / mid is used to compute the ceiling of pile/mid using integer arithmetic.

Complexity Analysis

Time Complexity: O(N * log M), where N is the number of piles and M is the maximum pile size. The binary search runs in about log M steps, and each step we compute the total hours in O(N). This is efficient even for large values of N and M.
Space Complexity: O(1), since the extra space used is minimal.

Edge Cases

Single Pile: If there is only one pile (e.g., piles = [10] and h = 5), then Koko must eat 10 bananas/hour to finish in time.
Plenty of Time: If h is very large (for example, much larger than the total number of bananas), Koko can eat as slowly as 1 banana per hour and still finish. The answer in such cases would be 1.
Huge Pile Sizes: If piles contain very large numbers, the binary search approach efficiently handles it, whereas a linear search would not.

Common Mistakes

Using floor division instead of ceiling when calculating hours (for example, using sum(pile // k) in Python). This underestimates the hours needed because any leftover bananas in a pile still require an entire extra hour.
Iterating through every possible speed (brute force) for large inputs, which is extremely slow. Remember that the feasible solution space is monotonic, which is why binary search works here.

Alternative Variations

Minimize Maximum Workload: Instead of time, imagine distributing piles among multiple workers to minimize the maximum bananas one worker has to eat. This is a similar load-balancing concept, often solved with binary search or greedy methods.
Split Array Largest Sum: A problem where you split an array into a given number of subarrays and aim to minimize the largest sum among these subarrays. This also involves binary searching for an optimal threshold.

Split Array Largest Sum – Partition an array into subarrays such that the largest subarray sum is minimized (uses binary search or dynamic programming).
Capacity To Ship Packages Within D Days – Find the minimum capacity needed to ship packages within a deadline (binary search for the correct capacity).
Find Smallest Divisor Given a Threshold – Determine the smallest number you can divide all elements by so that the sum of the quotients is within a given threshold (binary search on the divisor).

875. Koko Eating Bananas - Detailed Explanation

Problem Statement

Examples

Example 1

Example 2

Example 3

Constraints

Hints to Solve the Problem

Approach 1: Brute Force (Try All Speeds)

Explanation

Python Code

Complexity Analysis

Approach 2: Optimized Binary Search

Explanation

Python Code

Java Code (Binary Search Approach)

Complexity Analysis

Edge Cases

Common Mistakes

Alternative Variations

Related Problems for Practice