13. Koko Eating Bananas
β GFG solution to the Koko Eating Bananas problem: find minimum eating speed to finish all banana piles within k hours using binary search. π
The problem can be found at the following link: π Question Link
π§© Problem Description
Koko is given an array arr[]
, where each element represents a pile of bananas. She has exactly k
hours to eat all the bananas.
Each hour, Koko can choose one pile and eat up to s
bananas from it:
If the pile has at least
s
bananas, she eats exactlys
bananasIf the pile has fewer than
s
bananas, she eats the entire pile in that hourKoko can only eat from one pile per hour
Your task is to find the minimum value of s (bananas per hour) such that Koko can finish all the piles within k
hours.
π Examples
Example 1
Input: arr[] = [5, 10, 3], k = 4
Output: 5
Explanation: Koko eats at least 5 bananas per hour to finish all piles within 4 hours,
as she can consume each pile in 1 + 2 + 1 = 4 hours.
Example 2
Input: arr[] = [5, 10, 15, 20], k = 7
Output: 10
Explanation: At 10 bananas per hour, Koko finishes in 6 hours (1+1+2+2),
just within the limit 7.
π Constraints
$1 \le \text{arr.size()} \le 10^5$
$1 \le \text{arr}[i] \le 10^6$
$\text{arr.size()} \le k \le 10^6$
β
My Approach
The optimal approach uses Binary Search on the answer space to find the minimum eating speed:
Binary Search on Speed
Define Search Space:
Minimum speed:
1
banana per hour (lowest possible)Maximum speed:
max(arr)
bananas per hour (eat largest pile in 1 hour)
Binary Search Logic:
For each mid speed, calculate total hours needed
If hours β€ k, try smaller speed (search left half)
If hours > k, need faster speed (search right half)
Calculate Hours for Given Speed:
For each pile of size
pile
, hours needed =βpile/speedβ
Use ceiling division:
(pile + speed - 1) / speed
Optimization:
The answer is the minimum speed that allows finishing within k hours
π Time and Auxiliary Space Complexity
Expected Time Complexity: O(n Γ log(max_pile)), where n is the array size. Binary search takes O(log(max_pile)) iterations, and each iteration calculates hours in O(n) time.
Expected Auxiliary Space Complexity: O(1), as we only use constant extra space for variables (excluding the input array).
π§βπ» Code (C++)
class Solution {
public:
int kokoEat(vector<int>& arr, int k) {
int lo = 1, hi = *max_element(arr.begin(), arr.end());
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
int hours = 0;
for (int pile : arr) {
hours += (pile + mid - 1) / mid;
}
if (hours <= k)
hi = mid;
else
lo = mid + 1;
}
return lo;
}
};
π§βπ» Code (Java)
class Solution {
public int kokoEat(int[] arr, int k) {
int lo = 1, hi = 0;
for (int pile : arr) hi = Math.max(hi, pile);
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
int hours = 0;
for (int pile : arr) {
hours += (pile + mid - 1) / mid;
}
if (hours <= k) hi = mid;
else lo = mid + 1;
}
return lo;
}
}
π Code (Python)
class Solution:
def kokoEat(self, arr, k):
lo, hi = 1, max(arr)
while lo < hi:
mid = (lo + hi) // 2
hours = sum((pile + mid - 1) // mid for pile in arr)
if hours <= k:
hi = mid
else:
lo = mid + 1
return lo
π§ Contribution and Support
For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: π¬ Any Questions?. Let's make this learning journey more collaborative!
β If you find this helpful, please give this repository a star! β
πVisitor Count
Last updated