The O(n) Club: Koko Eating Bananas — Why Monkeys Ace Coding Interviews

The O(n) Club: Koko Eating Bananas — Why Monkeys Ace Coding Interviews

⚡ TL;DR

Banana-eating is serious work, apparently. Koko wants to finish N banana piles in H hours, and can only work on one pile per hour—no multitasking, no sneaky cross-pile bites. What’s her slowest possible eating speed (bananas/hour) so she makes it in time? Don’t iterate every k; use binary search before your interviewer switches you out for a chimp.

// Brute force way (please don't actually use this at work):
int maxPile = Arrays.stream(piles).max().getAsInt();
for (int k = 1; k <= maxPile; k++) {
    int hours = 0;
    for (int pile : piles)
        hours += Math.ceil((double) pile / k);
    if (hours <= h) return k;
}
// But we can do better — much better.

🧠 How Devs Usually Mess This Up

Common moves include linearly trying every possible k, driving up your runtime and driving down your interviewer’s faith in humanity. Some think if you eat a bit from every pile each hour you win. Not in this jungle. ‘One hour, one pile, as much as you can stomach’, says Koko. Don’t get clever with greedy methods—binary search is the upgrade you need.

🔍 What’s Actually Going On

At its core, the problem is a sneaky “binary search on the answer” interview classic. For any proposed speed k, if Koko can finish, she’ll always finish in time for speeds above k. This creates a tidy monotonic ‘can/can’t’ boundary. To check if a speed is fast enough, sum ceil(pile / k) hours for every pile. If the total fits in H, k is a candidate—then try slower speeds!

🛠️ PseudoCode

• Set left = 1, right = max(piles)
• While left < right:
• Set mid = (left + right)/2
• Compute total hours if eating at speed mid
• If hours <= h: try slower (right = mid)
• Else: not fast enough (left = mid + 1)
• Return left — slowest speed that works (and makes HR happy)

// Is k fast enough?
int hours = 0;
for (int pile : piles)
    hours += (pile + k - 1) / k; // Integer math for ceiling
return hours <= h;

💻 The Code

public int minEatingSpeed(int[] piles, int h) {
    int left = 1, right = Arrays.stream(piles).max().getAsInt();
    while (left < right) {
        int mid = left + (right - left) / 2;
        int hours = 0;
        for (int pile : piles)
            hours += (pile + mid - 1) / mid;
        if (hours <= h) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• No, you can’t chew on multiple piles in one hour. Koko is strictly FIFO (Fruit In, Fruit Out).
• If you’re off-by-one in your binary bounds, you’ll spend eternity debugging while Koko finishes lunch.
• Speed range is always [1, max pile]. Eating faster than the biggest pile is as wasteful as ordering Uber Eats to your neighbor’s house.
• Time? O(n log maxPile). Not O(n^2). Your future self will thank you.

🧠 Interviewer Brain-Tattoo

“If you linearly try every speed, congrats—next interview you’ll be eating the bananas, not coding them.”