Koko Eating Bananas

This one teaches a trick that feels like magic the first time you see it. You are not searching inside an array here. You are searching for the answer itself. The interviewer wants to see if you can spot when binary search applies even though there is no sorted array in sight. That idea is called binary search on the answer, and it unlocks a whole class of problems.

🎯 The Problem

Koko eats bananas from piles within a time limit. The rules:

• There are some piles. Each pile has a number of bananas.
• A guard is away for h hours.
• Koko picks one eating speed k. That is how many bananas she eats per hour.
• Each hour she eats from one pile only, up to k bananas.
• If a pile has fewer than k bananas left, she eats it all and waits out the rest of that hour.
• She does not start another pile in the same hour.
• Find the smallest speed k that finishes every pile within h hours.

Let us say the piles are [3, 6, 7, 11] and h is 8. The smallest speed that works is 4. At speed 4 the pile of 3 takes 1 hour. The pile of 6 takes 2 hours. The pile of 7 takes 2 hours. The pile of 11 takes 3 hours. That adds up to 8 hours, which fits.

Input:  piles = [3, 6, 7, 11], h = 8
Output: 4

Explanation: at speed 4 the hours are 1 + 2 + 2 + 3 = 8, which is within h = 8

Here is the key thing to notice. A bigger speed never needs more hours. So the speeds split into “too slow” and “fast enough”, and we want the first speed that is fast enough.

Here is the answer space. Speeds below 4 need too many hours. Speed 4 and above all finish in time. We want the boundary.

🐢 Approach 1: Try Every Speed (Brute Force)

Test each speed from slow to fast until one finishes in time.

The idea:

• Start at speed 1.
• Add up the hours that speed needs across all piles.
• If it fits within h, that speed is the answer.
• If not, try speed 2, then 3, and so on.

How it works:

• This is a linear scan over the possible speeds.
• A linear scan tries each value in order until one works.
• It always lands on the right speed.

Why it is weak:

• The top speed you ever need is the biggest pile.
• If the biggest pile has a million bananas, you might try a million speeds.
• For each speed you re-add all the piles.
• Time is O(n times max pile), where n is the number of piles. Too slow.

Here is the try-every-speed code:

import math


def min_eating_speed(piles, h):
    for speed in range(1, max(piles) + 1):
        hours = sum(math.ceil(pile / speed) for pile in piles)
        if hours <= h:
            return speed

⚡ Approach 2: Binary Search on the Answer (Best)

The speeds split into too-slow and fast-enough, so binary search the speed itself.

The idea:

• Speeds run from 1 up to the biggest pile, already in order.
• Every speed below the answer is too slow.
• Every speed from the answer up is fast enough.
• That clean split is what binary search needs.

The feasibility check:

• A feasibility check just tests whether one guessed speed works.
• For a pile of size p at speed mid, the hours are p divided by mid, rounded up.
• Round up because a leftover bit of a pile still costs a full hour.
• Add the hours for all piles. Compare with h.

How it works:

• Keep lo at 1, the slowest speed.
• Keep hi at the biggest pile, since no faster speed is ever needed.
• Pick the middle speed mid.
• If mid fits within h, a slower speed might still work, so move hi to mid.
• If mid does not fit, it is too slow, so move lo to mid + 1.
• Stop when lo meets hi. That value is the smallest speed that works.

Why it is fast:

• Each step throws away half the speeds.
• About log of the biggest pile rounds, each checking all piles.
• Time is O(n times log of max pile).

Here is a dry run on [3, 6, 7, 11] with h = 8. Watch lo, mid and hi close in on speed 4.

Steps to Solve

1. Set lo to 1 and hi to the largest pile.
2. While lo is less than hi, keep narrowing the window.
3. Find the middle speed mid as lo + (hi - lo) / 2.
4. Add up the hours at speed mid. For each pile, add its size divided by mid, rounded up.
5. If the total hours are within h, speed mid fits, so move hi to mid.
6. If the total hours go over h, speed mid is too slow, so move lo to mid + 1.
7. When lo equals hi, that is the smallest speed. Return it.

#include <stdio.h>

// hours needed to eat all piles at a given speed
long hoursNeeded(int piles[], int n, int speed) {
    long hours = 0;
    for (int i = 0; i < n; i++) {
        hours += (piles[i] + speed - 1) / speed; // divide, round up
    }
    return hours;
}

int minEatingSpeed(int piles[], int n, int h) {
    int lo = 1, hi = 0;
    for (int i = 0; i < n; i++) {
        if (piles[i] > hi) hi = piles[i];   // hi is the biggest pile
    }
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;       // middle speed
        if (hoursNeeded(piles, n, mid) <= h) {
            hi = mid;                        // fits, try slower
        } else {
            lo = mid + 1;                    // too slow
        }
    }
    return lo;                                // smallest speed that fits
}

int main(void) {
    int piles[] = {3, 6, 7, 11};
    int h = 8;
    printf("%d\n", minEatingSpeed(piles, 4, h));
    return 0;
}

4

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

long hoursNeeded(vector<int>& piles, int speed) {
    long hours = 0;
    for (int p : piles) {
        hours += (p + speed - 1) / speed; // divide, round up
    }
    return hours;
}

int minEatingSpeed(vector<int>& piles, int h) {
    int lo = 1, hi = *max_element(piles.begin(), piles.end());
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;     // middle speed
        if (hoursNeeded(piles, mid) <= h) {
            hi = mid;                      // fits, try slower
        } else {
            lo = mid + 1;                  // too slow
        }
    }
    return lo;                              // smallest speed that fits
}

int main() {
    vector<int> piles = {3, 6, 7, 11};
    int h = 8;
    cout << minEatingSpeed(piles, h) << endl;
    return 0;
}

4

public class Koko {
    static long hoursNeeded(int[] piles, int speed) {
        long hours = 0;
        for (int p : piles) {
            hours += (p + speed - 1) / speed; // divide, round up
        }
        return hours;
    }

    public static int minEatingSpeed(int[] piles, int h) {
        int lo = 1, hi = 0;
        for (int p : piles) {
            if (p > hi) hi = p;            // hi is the biggest pile
        }
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;  // middle speed
            if (hoursNeeded(piles, mid) <= h) {
                hi = mid;                  // fits, try slower
            } else {
                lo = mid + 1;              // too slow
            }
        }
        return lo;                          // smallest speed that fits
    }

    public static void main(String[] args) {
        int[] piles = { 3, 6, 7, 11 };
        int h = 8;
        System.out.println(minEatingSpeed(piles, h));
    }
}

4

import math


def hours_needed(piles, speed):
    return sum(math.ceil(p / speed) for p in piles)  # round each pile up


def min_eating_speed(piles, h):
    lo, hi = 1, max(piles)
    while lo < hi:
        mid = lo + (hi - lo) // 2          # middle speed
        if hours_needed(piles, mid) <= h:
            hi = mid                       # fits, try a slower speed
        else:
            lo = mid + 1                   # too slow, go faster
    return lo                               # smallest speed that fits


piles = [3, 6, 7, 11]
h = 8
print(min_eating_speed(piles, h))

4

function hoursNeeded(piles, speed) {
  let hours = 0;
  for (const p of piles) {
    hours += Math.ceil(p / speed); // round each pile up
  }
  return hours;
}

function minEatingSpeed(piles, h) {
  let lo = 1;
  let hi = Math.max(...piles);
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2); // middle speed
    if (hoursNeeded(piles, mid) <= h) {
      hi = mid;       // fits, try slower
    } else {
      lo = mid + 1;   // too slow
    }
  }
  return lo;          // smallest speed that fits
}

const piles = [3, 6, 7, 11];
const h = 8;
console.log(minEatingSpeed(piles, h));

4

Let us walk through the Python version line by line, so the “search on the answer” idea sticks.

The function hours_needed(piles, speed) is the feasibility check. The line return sum(math.ceil(p / speed) for p in piles) adds up the hours. For each pile p, math.ceil(p / speed) is the pile size divided by the speed, rounded up. We round up because any leftover bananas still cost a full hour.

The line lo, hi = 1, max(piles) sets the speed range. The slowest useful speed is 1. The fastest you ever need is the biggest pile, because at that speed every pile takes just one hour.

The line while lo < hi: shrinks the speed window until the two edges meet on one speed.

The line mid = lo + (hi - lo) // 2 picks the middle speed to test. Same overflow-safe middle as plain binary search.

The line if hours_needed(piles, mid) <= h: runs the feasibility check at speed mid. If the hours fit within h, then mid works. But a slower speed might also work, so we are not done. We set hi = mid and keep mid in the window.

The else branch means speed mid is too slow. The hours went over h. So we set lo = mid + 1 to force a faster speed.

When the loop ends, lo and hi point at the same speed. The line return lo hands back the smallest speed that finishes in time.

⏱️ Time and Space Complexity

The brute force tries every speed up to the biggest pile, and checks all piles each time. That is O(n times max pile). Binary search on the answer only tries about log of the biggest pile speeds, and checks all piles each time. So it is O(n times log of max pile). Both use only a few variables, so the space is O(1).

🧩 Key Takeaways

• ✅ You are searching for the answer speed, not searching inside an array.
• ✅ The speeds split into too-slow and fast-enough, which is perfect for binary search.
• ✅ Keep lo at 1 and hi at the biggest pile, since no faster speed is ever needed.
• ✅ The feasibility check adds up hours, rounding each pile up, and compares with h.
• ✅ This runs in O(n times log of max pile), far faster than trying every speed.

🚀 What’s Next?

• Binary Search
• Find Minimum in Rotated Sorted Array