Koko Eating Bananas
Ramayana — Hanuman's Minimum Speed — The Slowest Pace to Finish Before the Return
न अत्यधिक वेगः — न अत्यल्प वेगः। न्यूनतमः वेगः यः कार्यं समयेन पूरयेत् — तत् खोजो॥
*Not too fast, not too slow. The minimum speed that completes the task in time — find that.*
The Story
Koko has piles of bananas and h hours to eat them all. She eats at k bananas/hour (eats one pile per hour, rounding up if pile > k). Find the minimum k to eat all bananas within h hours.
For `piles = [3,6,7,11]`, h=8: answer k=4. At k=4: hours = ceil(3/4)+ceil(6/4)+ceil(7/4)+ceil(11/4) = 1+2+2+3 = 8 ≤ 8 ✓
**Binary search on the answer (k):** - Range: k ∈ [1, max(piles)] - For each k: hours = sum(ceil(pile/k)) = sum((pile+k-1)/k) - Find minimum k such that hours ≤ h
This is the "Binary Search on Answer" pattern — instead of searching in the input array, we search in the answer space!
```java int lo=1, hi=max(piles); while (lo < hi) { int mid = (lo+hi)/2; long hrs = 0; for (int p : piles) hrs += (p+mid-1)/mid; if (hrs <= h) hi = mid; // k is feasible, try smaller else lo = mid+1; // k too small, need faster } return lo; ```
**Why `hi = mid` not `hi = mid-1`?** When hrs <= h, mid is a valid answer (feasible). But we want the MINIMUM k, so we continue searching left (hi=mid). Like bs-6/bs-8, we save mid as a candidate.
Trace `[3,6,7,11]`, h=8: - lo=1,hi=11,mid=6: hrs=1+1+2+2=6 ≤ 8 → hi=6 - lo=1,hi=6,mid=3: hrs=1+2+3+4=10 > 8 → lo=4 - lo=4,hi=6,mid=5: hrs=1+2+2+3=8 ≤ 8 → hi=5 - lo=4,hi=5,mid=4: hrs=1+2+2+3=8 ≤ 8 → hi=4 - lo==hi=4 → return 4 ✓
The Incremental Speed Finder
Try k=1,2,3,... until hours <= h. O(n × max_pile).
public int minEatingSpeedBruteForce(int[] piles, int h) {
for (int k = 1; ; k++) {
long hours = 0;
for (int p : piles) hours += (p + k - 1) / k;
if (hours <= h) return k;
}
}Hanuman's Answer-Space Binary Search
public int minEatingSpeed(int[] piles, int h) {
int lo = 1, hi = 0;
for (int p : piles) hi = Math.max(hi, p);
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
long hours = 0;
for (int p : piles) hours += (p + mid - 1) / mid;
if (hours <= h) hi = mid; // Feasible: try smaller k
else lo = mid + 1; // Infeasible: need larger k
}
return lo;
}Step-by-Step Walkthrough
[1,1,1,1], h=4 → minimum k=1 lo=1,hi=1 → return 1 immediately ✅ [1000000000], h=2 lo=1,hi=1e9. Binary search finds k=500000000 (ceil(1e9/5e8)=2) ✅
Deep Insight
**Binary Search on Answer** — the most powerful extension of binary search! Instead of searching in an input array, we search in the ANSWER SPACE. Condition for feasibility: `hours <= h`. The feasibility function is monotone: if k works, k+1 also works. This monotonicity is what makes binary search applicable.
**The `ceil` trick:** `ceil(a/b) = (a+b-1)/b` using integer arithmetic. Avoids floating point.
**Same pattern as bs-12 through bs-17:** All are "binary search on answer" problems where we check feasibility for each candidate answer.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n × max) | O(1) | Try each k from 1 to max |
| Optimal | O(n log max) | O(1) | Binary search over [1,max_pile], O(n) feasibility check per step |
Pattern Recognition
✅ Binary search on the ANSWER (not the input array) ✅ Monotone feasibility function ✅ Feasible: try smaller (hi=mid); Infeasible: try larger (lo=mid+1) ✅ Return lo when converged **LeetCode Trigger Phrases:** → "minimum speed/capacity/pages" to complete task → Any optimization with a checkable feasibility condition → "Find minimum X such that condition holds"
Bhagavad Gita 6.17
युक्ताहारविहारस्य युक्तचेष्टस्य कर्मसु। युक्तस्वप्नावबोधस्य योगो भवति दुःखहा॥
For one who is regulated in eating, recreation, work, sleep, and wakefulness — yoga destroys all suffering.
Connection: Koko seeks the minimum regulated speed — not the frantic maximum, not the impossibly slow minimum, but the exact balance point where the task completes in time. Like the Gita's yoga of regulated action (not too much, not too little), the binary search finds the precise minimum speed where sufficiency meets efficiency. The feasibility check at each midpoint embodies the yogic principle of measured, purposeful action.