Problem Statement
Koko loves to eat bananas. There are n piles of bananas, the ith pile has piles[i] bananas. The guards have gone and will come back in h hours.
Koko can decide her bananas-per-hour eating speed k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has fewer than k bananas, she eats all of them instead and will not eat any more bananas during that hour.
Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.
Return the minimum integer k such that she can eat all the bananas within h hours.
Example 1
- Input:
piles = [3,6,7,11], h = 8
- Output:
4
Example 2
- Input:
piles = [30,11,23,4,20], h = 5
- Output:
30
Example 3
- Input:
piles = [30,11,23,4,20], h = 6
- Output:
23
Objective
Complete the function minEatingSpeed() which takes the array piles[] and integer h as input and returns the minimum speed k needed.
Expected Complexity
- Time Complexity: O(n log m), where
m = max(piles)
- Space Complexity: O(1)
Approaches
Brute Force
Idea
The brute force approach involves trying every possible speed k from 1 to max(piles) and checking whether Koko can finish all the bananas within h hours. This is inefficient.
Steps
- Iterate over all possible values of
k from 1 to max(piles).
- For each
k, simulate the eating process and check if all bananas can be eaten within h hours.
Time Complexity
Space Complexity
Example Code
Not provided due to inefficiency.
Dry Run
Skipped due to inefficiency.
Efficient Approach
Idea
Use binary search to find the optimal eating speed k. Define l = 1 and r = max(piles). Check the feasibility of k using a helper function check() that determines if Koko can finish all bananas at a given speed.
Steps
- Initialize
l = 1 and r = max(piles).
- Perform binary search:
- Set
mid = (l + r) / 2.
- Use
check(mid) to verify if Koko can finish eating all bananas within h hours.
- Adjust
l and r based on the result.
- Return the minimum possible
k.
Time Complexity
- O(n log m), where
m is max(piles).
Space Complexity
Example Code
Dry Run
- For
piles = [3,6,7,11], h = 8:
- Binary search will progressively narrow down to
4 as the optimal speed.
Example Test Cases
-
Test Case 1
- Input:
piles = [3,6,7,11], h = 8
- Output:
4
-
Test Case 2
- Input:
piles = [30,11,23,4,20], h = 5
- Output:
30
-
Test Case 3
- Input:
piles = [30,11,23,4,20], h = 6
- Output:
23
Complexity Analysis
Brute Force Approach
- Time Complexity: O(n * max(piles))
- Space Complexity: O(1)
Efficient Approach
- Time Complexity: O(n log m)
- Space Complexity: O(1)
Conclusion
The binary search-based approach efficiently determines the minimum eating speed k that allows Koko to eat all bananas within h hours, making it a much more practical solution compared to the brute force method.