Koko Eating Bananas

1. Problem & Core Objective

Koko eats bananas at k per hour. Each hour she picks one pile and eats up to k from it; if a pile has fewer than k left, she finishes it and waits out the hour. Given piles and h hours, return the minimum k that lets her finish in time.

piles = [3,6,7,11], h = 8   →  4
piles = [30,11,23,4,20], h = 5   →  30
piles = [30,11,23,4,20], h = 6   →  23

Constraints: 1 <= piles.length <= 10^4 · piles.length <= h <= 10^9 · 1 <= piles[i] <= 10^9

What's actually being tested: whether you notice you're not searching the array at all. n is small but the values reach 10^9 — that mismatch is the signal to binary search the answer space. It's the first problem in the 150 where that reading is required.

2. First-Principles Thought Process

Read the constraint mismatch

n <= 10^4 but piles[i] <= 10^9. An O(n log n) sort would be trivial and useless — sorting the piles tells you nothing about the right speed.

The huge value range is the hint. What has 10^9 possible values here? The answer: k ranges from 1 to max(piles).

Reframe

Don't ask "what's the answer". Ask a yes/no question you can evaluate cheaply:

"Can Koko finish at speed k?"

That's O(n) — sum the hours each pile needs. And the answer to it is monotonic: if speed 5 works, so does 6, 7, and everything above. Faster eating never requires more hours.

That monotonicity is precisely the false…false,true…true structure binary search needs. Without it the technique would be invalid, so it's worth stating explicitly rather than assuming.

Hours at a given speed

A pile of p bananas at speed k takes ceil(p / k) hours — she can't share an hour between piles, so a remainder still costs a full hour.

p = 7, k = 3  →  ceil(7/3) = 3 hours   (3, 3, 1)

Integer ceiling without floating point: (p + k - 1) / k.

The search range

• Lower bound 1 — she must eat something.
• Upper bound max(piles) — eating the largest pile per hour always finishes in n hours, and h >= n is guaranteed. Any higher speed is wasted.

3. Solution Paths

Approach 1 — Try every speed (brute force)

public int minEatingSpeed(int[] piles, int h) {
    int max = 0;
    for (int p : piles) max = Math.max(max, p);

    for (int k = 1; k <= max; k++) {          // try speeds in increasing order
        if (hoursNeeded(piles, k) <= h) return k;   // first one that works is the answer
    }
    return max;
}

private long hoursNeeded(int[] piles, int k) {
    long hours = 0;
    for (int p : piles) hours += (p + k - 1) / k;    // ceiling division
    return hours;
}

Scan speeds from 1 upward and return the first that fits.

• Time O(max(piles) · n) — up to 10^9 × 10^4 = 10^13 · Space O(1)

Counter-questions on this approach

⭐ "You're scanning candidate speeds in increasing order. What does that tell you about the structure?"

That the feasibility check is monotonic — I stop at the first speed that works because I know every larger speed also works. But that's exactly the property binary search needs. If I'm relying on it to justify stopping early, I should be exploiting it to skip rather than stepping one at a time.

"How slow is this really?"

max(piles) reaches 10^9 and each check is O(n) at 10^4, so 10^13 operations worst case. Not borderline — hopeless.

"Is hoursNeeded returning long necessary, or defensive?"

Necessary. At k = 1 the hours equal the total bananas, which can be 10^4 × 10^9 = 10^13 — far beyond int. This overflows silently and wraps negative, so the comparison hours <= h would spuriously succeed and return 1. It's a real bug, not a precaution.

Approach 2 — Binary search the answer (optimal)

public int minEatingSpeed(int[] piles, int h) {
    int lo = 1, hi = 0;
    for (int p : piles) hi = Math.max(hi, p);        // fastest useful speed

    while (lo < hi) {                                 // HALF-OPEN: hi is a live candidate
        int mid = lo + (hi - lo) / 2;

        if (hoursNeeded(piles, mid) <= h) hi = mid;   // fits — try slower
        else                              lo = mid + 1;  // too slow — must speed up
    }
    return lo;                                        // lo == hi == the boundary
}

private long hoursNeeded(int[] piles, int k) {
    long hours = 0;
    for (int p : piles) hours += (p + k - 1) / k;
    return hours;
}

Trace — piles = [3,6,7,11], h = 8. Range starts [1, 11].

• Time O(n · log(max(piles))) — about 10^4 × 30 · Space O(1)

Counter-questions on this approach

⭐ "Why is binary search valid here? The speeds aren't an array you're given."

Binary search doesn't need an array — it needs an ordered space and a monotonic predicate. The speeds 1..max are ordered, and "finishes within h hours" is monotonic: faster never needs more hours. So the predicate is false for a prefix of speeds and true for the rest, and I'm finding that boundary.

If the predicate weren't monotonic the whole technique would be invalid — no index fixing would save it. That's the property to check before reaching for this.

⭐ "State your complexity precisely."

O(n · log(max(piles))). The log is over the value range, not the array length — that's the distinguishing feature of searching the answer space. Roughly 10^4 × 30 = 3 × 10^5 operations, versus 10^13 for the scan.

"Why (p + k - 1) / k rather than Math.ceil((double) p / k)?"

Integer arithmetic is exact. double has 53 bits of mantissa, and with values to 10^9 the division can land a hair below an integer and round the wrong way. (p + k - 1) / k pushes any non-zero remainder up to the next whole hour with no floating point at all.

"Why half-open bounds here rather than the inclusive convention?"

Because this is a boundary search, not an exact-match search. I want the smallest k that works, and hi = mid keeps mid alive as a candidate when it satisfies the predicate. With inclusive bounds and hi = mid - 1 I'd discard the answer the moment I found it. Different question, different convention.

"How do you know the loop terminates?"

mid is strictly less than hi when lo < hi, because integer division rounds down. So hi = mid strictly decreases hi, and lo = mid + 1 strictly increases lo. The range shrinks every iteration.

Approach 3 — Tighter lower bound (a refinement, not a fix)

You can start lo at ceil(totalBananas / h) rather than 1 — she can't possibly go slower than the average rate needed.

long total = 0;
for (int p : piles) total += p;
int lo = (int) Math.max(1, (total + h - 1) / h);

Counter-questions on this approach

⭐ "Does this change the complexity?"

No — it's still O(n log(max)). Binary search over 10^9 candidates takes 30 steps; over 10^8 it takes 27. Shaving the range barely moves a logarithm. It's a micro-optimization that adds a line of arithmetic and an overflow risk in total, so I'd skip it unless asked.

"Is the bound even correct?"

Yes — each hour eats at most k bananas, so finishing total bananas in h hours requires k >= total/h. But note it's only a lower bound on the answer, not the answer: piles can't be shared, so the real k is usually higher.

Comparison

4. Why the Optimal Wins

10^13 operations versus 3 × 10^5 — a factor of roughly 30 million.

The saving isn't from a cleverer feasibility check; it's from checking far fewer candidates. The scan tests every speed in order; binary search tests 30 of them and proves the rest are unnecessary.

Why O(n log max) is essentially optimal here. Every pile must be read to evaluate any candidate, so a single check costs O(n). And distinguishing max possible answers needs log₂(max) bits of information. So n log(max) is the natural floor for this approach.

The framing worth keeping:

When the array is small but the value range is huge, you're probably searching the answer, not the array.

The recipe is always the same: define a yes/no predicate over candidate answers, verify it's monotonic, bound the range, and binary search the boundary. It solves Split Array Largest Sum, Capacity to Ship Packages, Minimize Max Distance, and Swim in Rising Water — where the predicate is "is the end reachable at water level t", checked by BFS.

5. Java Prerequisites

Integer ceiling division

(p + k - 1) / k          // ceil(p/k) for positive p, k — exact
Math.ceil((double) p / k)  // floating point — precision risk at 10^9

Overflow in the hour count

long hours = 0;
for (int p : piles) hours += (p + k - 1) / k;

At k = 1, hours equals the total bananas — up to 10^4 × 10^9 = 10^13. An int accumulator wraps negative and the comparison silently passes. See 03.

Note p + k - 1 itself is safe: both are at most 10^9, so the sum is under 2^31.

Half-open boundary search

while (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    if (feasible(mid)) hi = mid;      // keep mid — it might be the answer
    else               lo = mid + 1;  // discard mid
}
return lo;

The template for every "smallest value satisfying a condition" problem.

6. Interview Communication Guide

Clarifying questions: Can she eat from more than one pile per hour (no — that's what forces the ceiling)? Is h >= piles.length guaranteed (yes, so an answer always exists)? Return the speed or the hours?

The pitch

"The array is only 10⁴ but the values reach 10⁹ — that mismatch tells me I'm not searching the array, I'm searching the answer.

Instead of asking 'what's the minimum speed', I'll ask a yes/no question I can evaluate cheaply: can she finish at speed k? That's O(n) — sum ceil(pile / k) over the piles.

And that predicate is monotonic: faster eating never needs more hours. So it's false for slow speeds and true for everything from some boundary upward — and that boundary is the answer. That monotonicity is what licenses binary search; without it the technique wouldn't apply at all.

The range is 1 to max(piles), since eating the biggest pile per hour always finishes in n hours and h >= n. Binary search that range with half-open bounds, keeping mid alive when it's feasible.

O(n log(max)) — the log is over the value range, not the array. About 3 × 10⁵ operations versus 10¹³ for scanning every speed.

Two details: I'll use (p + k - 1) / k for the ceiling rather than floating point, and accumulate hours in a long — at k = 1 the total reaches 10¹³ and would overflow an int."

Edge cases to volunteer:

h == piles.length is the one to name — it forces k = max(piles), which confirms the upper bound is tight rather than arbitrary.

7. Follow-Up Questions — Modified Constraints

⭐ "What if she could eat from multiple piles in one hour?"

The ceiling disappears — the hours become ceil(total / k), so the answer is directly ceil(total / h) with no search at all. O(n). It's a good illustration that the one pile per hour rule is the entire source of difficulty: it's what makes the hour count non-linear in k.

"Minimum capacity to ship all packages within D days, preserving order." (LC 1011)

Same recipe. Predicate: "can these packages ship in D days with capacity c?" — greedily fill each day, O(n). Monotonic, since more capacity never needs more days. Range is [max(weights), sum(weights)] — note the lower bound is max, not 1, because a single package must fit.

"Split an array into k subarrays minimising the largest subarray sum." (LC 410)

Identical structure: predicate "can it be split into ≤ k parts with no part exceeding s", greedy check, range [max, sum]. This family is worth recognizing as one pattern rather than four problems.

"What if h could be smaller than the number of piles?"

Then it's impossible — she needs at least one hour per pile regardless of speed, since she can't combine piles. The constraints rule it out; without them I'd return -1 after checking h < n up front.

"What if the piles could be eaten in any order, or split across hours?"

Splitting across hours is the multi-pile case above. Reordering changes nothing — the hour count is a sum over piles and is order-independent. Worth stating, because it confirms the greedy check doesn't need sorting.