Koko Eating Bananas
Problem
Given an array piles where piles[i] is the number of bananas in the ith pile and an integer h representing hours, return the minimum integer k such that Koko can eat all bananas within h hours by eating k bananas per hour from one pile at a time.
- 1 ≤ piles.length ≤ 10⁴
- 1 ≤ piles[i] ≤ 10⁹
- piles.length ≤ h ≤ 10⁹
Example
piles = [3,6,7,11], h = 84At speed k=4, Koko eats as follows: - Hour 1: Eat 4 bananas from pile 1 (3 bananas), finishes pile 1 in 1 hour. - Hour 2: Eat 4 bananas from pile 2 (6 bananas), 2 hours total. - Hour 3: Eat remaining 2 bananas from pile 2, 3 hours total. - Hour 4: Eat 4 bananas from pile 3 (7 bananas), 4 hours total. - Hour 5: Eat remaining 3 bananas from pile 3, 5 hours total. - Hour 6: Eat 4 bananas from pile 4 (11 bananas), 6 hours total. - Hour 7: Eat 4 bananas from pile 4, 7 hours total. - Hour 8: Eat remaining 3 bananas from pile 4, 8 hours total. This is the minimum speed to finish within 8 hours.
Approach
Straightforward Solution
A brute-force approach tries all speeds from 1 to max(piles), computing hours needed for each. This is O(n * max(piles)) and is infeasible for large inputs due to the large search space.
Core Observation
The minimum eating speed k lies between 1 and the maximum pile size. For any candidate speed k, the total hours needed to finish all piles can be computed by summing the ceiling of pile size divided by k. This total hours function is monotonically decreasing with respect to k.
Path to Optimal
Recognizing the monotonic relationship between speed and hours needed enables binary search on k. By checking midpoints and adjusting the search space based on whether the total hours exceed h, the algorithm efficiently narrows down the minimum feasible speed.
Optimal Approach
Use binary search between 1 and max(piles). For each mid speed k, compute total hours by summing ceil(pile/k) for all piles. If total hours <= h, update result and search left half to find smaller feasible speeds. Otherwise, search right half. Return the smallest k found.
Time
O(n log m)
Where n is the number of piles and m is the maximum pile size. Each binary search iteration takes O(n) to compute total hours, and binary search performs O(log m) iterations.
Space
O(1)
Only a few variables are used for pointers and counters; no additional data structures scale with input size.
Pattern Spotlight
Binary Search (Search Space Reduction on Monotonic Function)
When the problem asks for a minimum or maximum value satisfying a monotonic condition, transform the problem into a decision problem and use binary search over the value domain to efficiently find the optimal solution.
Solution
| 1 | import math
|
| 2 |
|
| 3 | class Solution:
|
| 4 | def minEatingSpeed(self, piles: list[int], h: int) -> int:
|
| 5 | left, right = 1, max(piles)
|
| 6 | res = right
|
| 7 |
|
| 8 | while left <= right:
|
| 9 | k = (left + right) // 2
|
| 10 | hours = 0
|
| 11 | for p in piles:
|
| 12 | hours += math.ceil(p / k)
|
| 13 |
|
| 14 | if hours <= h:
|
| 15 | res = min(res, k)
|
| 16 | right = k - 1
|
| 17 | else:
|
| 18 | left = k + 1
|
| 19 |
|
| 20 | return res |
| 1 | import java.util.*; |
| 2 | |
| 3 | class Solution { |
| 4 | public int minEatingSpeed(int[] piles, int h) { |
| 5 | int left = 1; |
| 6 | int right = 0; |
| 7 | for (int pile : piles) { |
| 8 | right = Math.max(right, pile); |
| 9 | } |
| 10 | int res = right; |
| 11 | |
| 12 | while (left <= right) { |
| 13 | int k = (left + right) / 2; |
| 14 | int hours = 0; |
| 15 | for (int p : piles) { |
| 16 | hours += (p + k - 1) / k; // ceil division |
| 17 | } |
| 18 | |
| 19 | if (hours <= h) { |
| 20 | res = Math.min(res, k); |
| 21 | right = k - 1; |
| 22 | } else { |
| 23 | left = k + 1; |
| 24 | } |
| 25 | } |
| 26 | |
| 27 | return res; |
| 28 | } |
| 29 | } |
| 1 | #include <vector> |
| 2 | #include <algorithm> |
| 3 | |
| 4 | using namespace std; |
| 5 | |
| 6 | class Solution { |
| 7 | public: |
| 8 | int minEatingSpeed(vector<int>& piles, int h) { |
| 9 | int left = 1; |
| 10 | int right = *max_element(piles.begin(), piles.end()); |
| 11 | int res = right; |
| 12 | |
| 13 | while (left <= right) { |
| 14 | int k = left + (right - left) / 2; |
| 15 | long long hours = 0; |
| 16 | for (int p : piles) { |
| 17 | hours += (p + k - 1) / k; // ceil division |
| 18 | } |
| 19 | |
| 20 | if (hours <= h) { |
| 21 | res = min(res, k); |
| 22 | right = k - 1; |
| 23 | } else { |
| 24 | left = k + 1; |
| 25 | } |
| 26 | } |
| 27 | |
| 28 | return res; |
| 29 | } |
| 30 | }; |
| 1 | var minEatingSpeed = function(piles, h) { |
| 2 | let left = 1; |
| 3 | let right = Math.max(...piles); |
| 4 | let res = right; |
| 5 | |
| 6 | while (left <= right) { |
| 7 | let k = Math.floor((left + right) / 2); |
| 8 | let hours = 0; |
| 9 | for (let p of piles) { |
| 10 | hours += Math.ceil(p / k); |
| 11 | } |
| 12 | |
| 13 | if (hours <= h) { |
| 14 | res = Math.min(res, k); |
| 15 | right = k - 1; |
| 16 | } else { |
| 17 | left = k + 1; |
| 18 | } |
| 19 | } |
| 20 | |
| 21 | return res; |
| 22 | }; |
Step-by-Step Solution
Initialize Binary Search Boundaries and Result
| 5 | left, right = 1, max(piles)
|
| 6 | res = right
|
Objective
To set the initial search space for the eating speed between 1 and the largest pile size, and initialize the result to the upper bound.
Key Insight
The minimum speed cannot be less than 1 and cannot exceed the largest pile size, as eating faster than the largest pile is unnecessary. Initializing the result to the upper bound ensures a valid starting point for minimization.
Interview Quick-Check
Core Logic
Setting left to 1 and right to max(piles) defines the search space for the binary search over possible speeds.
State & Boundaries
Initializing result to right ensures that if no smaller speed satisfies the condition, the maximum pile size is returned.
Perform Binary Search to Find Minimum Feasible Speed
| 8 | while left <= right:
|
| 9 | k = (left + right) // 2
|
| 10 | hours = 0
|
| 11 | for p in piles:
|
| 12 | hours += math.ceil(p / k)
|
| 14 | if hours <= h:
|
| 15 | res = min(res, k)
|
| 16 | right = k - 1
|
| 17 | else:
|
| 18 | left = k + 1
|
Objective
To iteratively narrow down the search space by checking the feasibility of the mid speed and adjusting boundaries accordingly.
Key Insight
By computing the total hours needed at speed k and comparing it to h, the algorithm decides whether to search for smaller speeds (if feasible) or larger speeds (if not). This exploits the monotonicity of the hours function to efficiently converge on the minimal valid speed.
Interview Quick-Check
Core Logic
Calculate total hours for mid speed by summing ceil(pile/k) for all piles; if total hours <= h, update result and search left half; else search right half.
State & Boundaries
The loop continues while left <= right, ensuring all candidate speeds are considered.
Common Pitfalls & Bugs
Using integer division instead of ceiling can underestimate hours, leading to incorrect feasibility checks.
Complexity
Each iteration takes O(n) time to compute hours, and binary search performs O(log m) iterations, resulting in O(n log m) total time.
Return the Minimum Eating Speed Found
| 20 | return res |
Objective
To output the smallest speed k that allows Koko to finish eating within h hours.
Key Insight
After binary search completes, the stored result is guaranteed to be the minimal feasible speed due to the search narrowing and updates during the loop.
Interview Quick-Check
Core Logic
Returning the result after the binary search loop ensures the minimal speed satisfying the time constraint is output.
Line Analysis
This solution has 1 Critical line interviewers watch for.
hours += math.ceil(p / k)Add the ceiling of pile divided by k to the total hours.
This line is critical because it correctly models the time cost per pile using ceiling division, which is essential for accurate feasibility checks; using floor division would underestimate hours and break correctness.
left, right = 1, max(piles)Initialize the binary search boundaries: left at 1 and right at the maximum pile size.
The minimum eating speed must be at least 1 and cannot exceed the largest pile, as eating faster than the largest pile is unnecessary and does not reduce hours further.
if hours <= h:Check if total hours needed is within the allowed time h.
This condition determines if the current speed k is feasible, guiding the binary search direction.
return resReturn the minimal feasible eating speed found.
After binary search completes, the stored result is guaranteed to be the smallest speed that allows finishing within h hours.
k = (left + right) // 2Calculate the midpoint speed k as the candidate eating speed.
Choosing the midpoint divides the search space in half, enabling logarithmic convergence of the binary search.
for p in piles:Iterate over each pile to calculate hours needed at speed k.
Each pile contributes ceil(pile/k) hours, representing the number of full hours needed to finish that pile at speed k.
res = min(res, k)Update the result to the smaller feasible speed k.
Recording the minimal feasible speed found so far ensures the final answer is the smallest speed satisfying the time constraint.
right = k - 1Adjust the right boundary to search for smaller speeds.
Since k is feasible, searching the left half may find an even smaller feasible speed, refining the solution.
else:Handle the case where total hours exceed h, making k infeasible.
If k is too slow, increase the left boundary to search for faster speeds that reduce total hours.
left = k + 1Adjust the left boundary to search for larger speeds.
Increasing left discards infeasible speeds, focusing the search on speeds that might satisfy the time constraint.
res = rightInitialize the result variable to the upper boundary of the search space.
Setting result to right ensures a valid initial answer that will be updated to smaller feasible speeds during the search.
while left <= right:Start the binary search loop, continuing while the search space is valid.
The condition left <= right ensures all candidate speeds in the range are considered, enabling convergence to the minimal feasible speed.
hours = 0Initialize the hours counter for the current candidate speed.
Resetting hours to zero prepares to accumulate the total hours needed to finish all piles at speed k.
Test Your Understanding
Why is binary search applicable to the eating speed k in this problem?
Because the total hours needed to finish all piles is a monotonically decreasing function of k, allowing the use of binary search to find the minimum k that satisfies the time constraint.
Related Problems
Binary Search pattern
Don't just read it. Drill it.
Reconstruct Koko Eating Bananas from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Koko Eating Bananas drill