Koko Eating Bananas
Find the minimum eating speed that still finishes every pile before the deadline.
Problem Summary
Original task summary for this archive page. The official LeetCode prompt is linked in the header instead of being mirrored here.
Koko has several piles of bananas and a deadline in hours. She chooses one pile per hour and eats up to \(k\) bananas from it. The task is to find the smallest integer speed \(k\) that lets her finish on time.
The input is not sorted, but the answer is still a single integer that can be tested for feasibility.
Recognition Pattern
How to notice the underlying interview pattern before writing code.
This is binary search on the answer.
In interviews, recognize it when:
the question asks for the minimum or maximum integer answer
you can write a helper function that says whether a candidate answer works
once an answer works, every larger answer also works, or vice versa
Key Idea
The main invariant or observation that makes the clean solution work.
If Koko can finish with speed \(k\), then she can also finish with any speed larger than \(k\). That monotonic behavior is exactly what binary search needs.
So instead of testing every possible speed from \(1\) to the largest pile, binary-search that range and use a feasibility check: \[ \text{hours needed} = \sum \left\lceil \frac{pile}{k} \right\rceil \]
If the total hours fit within the deadline, try a smaller speed. Otherwise, increase the speed.
Step-by-step Reasoning
How to move from the obvious brute-force idea to the interview-ready solution.
The brute-force idea is straightforward: try every speed and stop at the first one that works. The problem is that the answer range can be large, so this wastes too many checks.
The key observation is not about the piles themselves. It is about the answer space. Speeds form a yes/no boundary:
too slow: impossible
fast enough: possible
Once you see that boundary, the input no longer needs to be sorted. You only need a reliable predicate and a finite search range, which here is \([1, \max(pile)]\).
Complexity
Time and memory costs for the implementation shown below.
Time: \(O(n \log M)\), where \(M\) is the largest pile
Space: \(O(1)\)
C++ Solution
The exact repository source used for this LeetCode solution page.
#include <algorithm>
#include <vector>
class Solution {
public:
int minEatingSpeed(std::vector<int>& piles, int h) {
int left = 1;
int right = *std::max_element(piles.begin(), piles.end());
while (left < right) {
const int middle = left + (right - left) / 2;
if (canFinish(piles, h, middle)) {
right = middle;
} else {
left = middle + 1;
}
}
return left;
}
private:
bool canFinish(const std::vector<int>& piles, int h, int speed) {
long long hoursNeeded = 0;
for (int pile : piles) {
hoursNeeded += (pile + speed - 1LL) / speed;
if (hoursNeeded > h) {
return false;
}
}
return true;
}
};
Common Pitfalls
Real implementation mistakes that show up often in interviews and submissions.
Using plain integer division for the hour count is wrong. You need ceiling division, which can be written as \((pile + k - 1) / k\).
The accumulated hour count can exceed 32-bit range, so use a 64-bit integer for the total.
When a speed works, do not stop immediately. Keep searching the left half for a smaller feasible answer.
Variants / Follow-ups
Nearby problems and the next generalization to learn once this pattern is stable.
This pattern appears again in Capacity To Ship Packages Within D Days, Split Array Largest Sum, and many scheduling or rate-limit problems.
The reusable skill is spotting a monotone feasibility predicate even when the original input is unsorted.
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.