Koko Eating Bananas: Find the Minimum Eating Speed

109.1k
0

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 of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour. 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

Explanation: If Koko eats at a speed of 4 bananas per hour, she takes 1 hour for the first pile, 2 hours for the second, 2 hours for the third, and 3 hours for the fourth. Total time is 1 + 2 + 2 + 3 = 8 hours, which exactly meets the 8-hour deadline.

Example 2

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

Output: 30

Explanation: With only 5 hours available for 5 piles, Koko must consume exactly one pile per hour. She needs a speed equal to the largest pile (30) to ensure even the biggest pile takes only 1 hour.

Brute Force Approach

The most direct idea is to try every possible eating speed. The slowest speed is 1 banana per hour. The fastest useful speed is the largest pile size, because eating faster than the largest pile does not reduce any pile below one hour.

For each speed, calculate how many hours are needed to finish all piles. The first speed that needs at most h hours is the answer.

This works because speeds are checked from smallest to largest, so the first valid speed is definitely the minimum valid speed.

Algorithm

  • Find the largest pile size. This becomes the highest useful speed because no pile needs more than its own size to finish in one hour.

  • Try every speed from 1 to the largest pile size. This checks speeds in increasing order so the first valid speed is the smallest one.

  • For each pile, calculate the hours needed using ceiling division. This is required because even a partly eaten pile still consumes a full hour.

  • If the total hours becomes greater than h, stop checking the current speed early because it has already failed.

  • Return the first speed whose total hours is less than or equal to h, because that is the smallest speed that allows Koko to finish on time.

Dry Run

Koko Eating Bananas Brute Dry Run

Koko Eating Bananas Brute Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
/*
Checks whether Koko can finish all piles
if she eats at the given speed.
*/
bool canFinish(vector<int>& piles, int speed, int h) {
// This stores the total hours needed for the current speed.
long long hours = 0;
for (int pile : piles) {
hours += (pile + speed - 1) / speed;
// If hours already cross h,
// this speed is too slow.
if (hours > h) {
return false;
}
}
// The speed works only when all piles finish within h hours.
return hours <= h;
}
public:
/*
Finds the minimum eating speed by trying
every possible speed one by one.
*/
int minEatingSpeed(vector<int>& piles, int h) {
// No useful speed needs to be larger than the biggest pile.
int maxPile = *max_element(piles.begin(), piles.end());
for (int speed = 1; speed <= maxPile; speed++) {
// The first working speed is the answer
// because speeds are checked from small to large.
if (canFinish(piles, speed, h)) {
return speed;
}
}
return maxPile;
}
};
// Driver code starts
int main() {
vector<int> piles = {3, 6, 7, 11};
int h = 8;
Solution obj;
cout << obj.minEatingSpeed(piles, h) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N x max(piles)), because every possible speed may be checked and each check can scan all piles.

Space Complexity: O(1), because constant space is used.

Optimal Approach

The important pattern is how the eating speed affects the required hours. If the speed is small, Koko eats fewer bananas per hour, so large piles take more hours. This may fail. If the speed is large, Koko eats more bananas per hour, so each pile takes fewer hours or the same number of hours. This makes the speed more likely to work.

So the possible speeds form a pattern like this: false, false, false, true, true, true

The task is to find the first true, meaning the smallest speed that finishes all piles within h hours.

Binary search fits perfectly because every failed speed tells that all smaller speeds will also fail, and every successful speed tells that a smaller answer may still exist on the left.

Algorithm

  • Set low to 1 because Koko must eat at least one banana per hour.

  • Set high to the largest pile size because that speed can finish any pile in one hour, and no larger speed is useful.

  • Pick the middle speed mid. This is treated as a possible eating speed, not as an array index.

  • Calculate how many hours are needed at speed mid by adding ceil(pile / mid) for every pile. Ceiling is needed because a partly eaten pile still takes a full hour.

  • If the total hours are less than or equal to h, mid is fast enough. Move high to mid because the answer might be this speed or a smaller one.

  • Otherwise, mid is too slow. Move low to mid + 1 because all speeds up to mid cannot finish in time.

  • When low and high meet, return that value because it is the smallest speed that works.

Dry Run

Koko Eating Bananas Optimal Dry Run

Koko Eating Bananas Optimal Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
/*
Checks whether Koko can finish all piles
if she eats at the given speed.
*/
bool canFinish(vector<int>& piles, int speed, int h) {
// This stores the total hours needed for the current speed.
long long hours = 0;
for (int pile : piles) {
hours += (pile + speed - 1) / speed;
// If hours already cross h,
// this speed is too slow.
if (hours > h) {
return false;
}
}
// The speed works only when all piles finish within h hours.
return hours <= h;
}
public:
/*
Finds the minimum eating speed using binary search
over all possible speed values.
*/
int minEatingSpeed(vector<int>& piles, int h) {
// The slowest possible eating speed is 1 banana per hour.
int low = 1;
// The largest pile is the fastest useful speed.
int high = *max_element(piles.begin(), piles.end());
while (low < high) {
// mid is the eating speed being tested right now.
int mid = low + (high - low) / 2;
// If mid works, try the left side for a smaller speed.
if (canFinish(piles, mid, h)) {
high = mid;
} else {
// If mid fails, all smaller speeds fail too.
low = mid + 1;
}
}
return low;
}
};
// Driver code starts
int main() {
vector<int> piles = {3, 6, 7, 11};
int h = 8;
Solution obj;
cout << obj.minEatingSpeed(piles, h) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N x log2(max(piles))), because each binary-search on answer range max(piles) take log(max(piles)) and check scans all piles once.

Space Complexity: O(1), because constant space is used.

Interview follow-up Questions

If Koko eats at a speed equal to the largest pile, she finishes that pile in exactly 1 hour. All other smaller piles will also naturally be finished in 1 hour each. Any speed higher than the maximum pile yields the exact same total hours, making it redundant to search beyond the maximum element.

Two PointerSortingBinary SearchArraysMaths

Read Similar Blogs

Arrays

Row wise traversal

Given a matrix with N rows and M columns, print all elements row by row from left to right. Input: mat = [[1, 2, 3], [4, 5, 6]] Output: 1 2 3 4 5 6 Explanation: First row prints as 1 2 3 , then sec...

61.7k
Arrays

Main Diagonal Print

Given a matrix with N rows and M columns, print all elements present on the main diagonal. Input: mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] Output: 1 5 9 Explanation: Main diagonal cells are mat[0][0...

67.1k
Arrays

Search Element in Matrix

Given a matrix with N rows and M columns and a target value X , search for X in the matrix. Return the position of the first occurrence of X as {row, col} . Return {-1, -1} when the target value is...

98.4k
Comments0