Loading…

mediumBinary SearchLC #875Frequently asked

Koko Eating Bananas

Q: How do you solve Koko Eating Bananas using the Linear Scan Over Speeds (Baseline) approach?

When to use it: Mention to expose the monotone feasibility idea, then replace the linear sweep with binary search. Try every speed from 1 upward; for each, sum `⌈pile / k⌉` over all piles and return the first `k` whose total is `≤ h`. **Why mention it.** It surfaces the core sub-routine — the feasibility test `hours(k) <= h` — and makes the monotonic behaviour visible: as `k` increases, the total hours never increase. **Why it's too slow.** `max(piles)` reaches `10⁹`, so a linear sweep is up to `10⁹ × 10⁴` operations. But the monotonicity we just noticed means we don't have to try every speed — we can binary search for the tipping point. Time complexity: O(n * max(piles)). Space complexity: O(1).

LCPractice

Binary Search · 5 of 16 · 10 min

Koko loves to eat bananas. There are n piles of bananas, the i-th pile has piles[i] bananas. The guards have gone and will come back in h hours.

Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile and eats k bananas from it. If the pile has fewer than k bananas, she eats all of them and will not eat any more bananas during that hour.

Return the minimum integer k such that she can eat all the bananas within h hours.

In plain English

We must pick the slowest constant speed k that still lets Koko clear every pile within h hours. A pile of size p takes ⌈p/k⌉ hours because a partial pile still costs a full hour. Total hours decreases (never increases) as k grows, so we binary search for the tipping point.

Examples

Example 1

Input: piles = [3, 6, 7, 11], h = 8
Output: 4
Note: At k=4: ceil(3/4)+ceil(6/4)+ceil(7/4)+ceil(11/4) = 1+2+2+3 = 8 ≤ 8. At k=3 it takes 1+2+3+4 = 10 > 8, so 4 is the minimum.

Example 2

Input: piles = [30, 11, 23, 4, 20], h = 5
Output: 30
Note: Only 5 hours for 5 piles, so each pile must be cleared in one hour → k must be at least the largest pile, 30.

Example 3

Input: piles = [30, 11, 23, 4, 20], h = 6
Output: 23
Note: With one spare hour, k=23 works: ceil values 2+1+1+1+1 = 6 ≤ 6.

Constraints

1 ≤ piles.length ≤ 10⁴
piles.length ≤ h ≤ 10⁹
1 ≤ piles[i] ≤ 10⁹

Clarifying questions4First question: Can Koko split one pile across hours or eat from multiple piles in one hour?Explore questions

Q1.Can Koko split one pile across hours or eat from multiple piles in one hour?
She eats from only one pile per hour, and a pile smaller than k still consumes the whole hour. That's why a pile costs ⌈p/k⌉ hours.
Q2.What's the valid range for k?
At least 1 (she must make progress) and at most max(piles) — any faster than that finishes each pile in one hour and adds nothing.
Q3.Is h always large enough for a solution to exist?
Yes — h ≥ piles.length, so even at the maximum useful speed (one pile per hour) she finishes, guaranteeing a feasible k exists.
Q4.How big can the numbers get — should I worry about overflow?
Yes in Java: up to 10⁴ piles, each costing up to 10⁹ hours, sums beyond int range. Use long for the hour accumulator.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

There is no sorted array to search — instead binary search on the *answer*: the eating speed k. 'Can Koko finish within h hours at speed k?' is monotone — if a speed works, every larger speed works too. Binary search k in [1, max(piles)]; for each candidate, sum ⌈pile / k⌉ hours and keep the smallest k whose total ≤ h. O(n log(max(piles))) time, O(1) space.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you recognise a 'minimize X subject to a monotone constraint' problem and binary search the answer space, rather than only knowing binary search as 'find element in sorted array'.

Where candidates slip

Computing hours with integer division (floor) instead of ceiling, setting the search range wrong (starting at 0, or hi too small), or overflowing the hour sum in Java.

How to stand out

State the monotonicity explicitly ('faster never hurts'), justify the [1, max] bounds, and use the smallest-feasible boundary template cleanly.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Linear Scan Over Speeds (Baseline)	`O(n * max(piles))`	`O(1)`	Mention to expose the monotone feasibility idea, then replace the linear sweep with binary search.	Read
2	Binary Search on the Answer (Optimal)Optimal	`O(n log(max(piles)))`	`O(1)`	The answer they want. Say 'I'll binary search the speed, not the array' and justify with monotonicity.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewCandidate speed k in [1, max(piles)]hours <= h?Yes (k works)No (too slow)Explore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Linear Scan Over Speeds (Baseline)

TimeO(n * max(piles))SpaceO(1)

Mention to expose the monotone feasibility idea, then replace the linear sweep with binary search.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

What's the slowest speed that could possibly work, and the fastest you'd ever need?

2Hint 2Explore hint

Try k = 1, 2, 3, ... and for each compute the total hours; return the first k that fits in h.

3Hint 3Explore hint

Correct, but max(piles) can be 10⁹, so sweeping every speed is far too slow — notice the hours only ever decrease as k grows.

A · Core idea

Try every speed from 1 upward; for each, sum ⌈pile / k⌉ over all piles and return the first k whose total is ≤ h.

Why mention it. It surfaces the core sub-routine — the feasibility test hours(k) <= h — and makes the monotonic behaviour visible: as k increases, the total hours never increase. Why it's too slow. max(piles) reaches 10⁹, so a linear sweep is up to 10⁹ × 10⁴ operations. But the monotonicity we just noticed means we don't have to try every speed — we can binary search for the tipping point.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

piles = [3, 6, 7, 11], h = 8

k=1

3+6+7+11 = 27 > 8

Statetoo slow

Final result4

C · Code with teaching comments

Reference implementation previewpublic 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++) { long hours = 0;Explore the full code

solution.javaJava

Linear Scan Over Speeds (Baseline) — reference

2 teaching notes

1
public int minEatingSpeed(int[] piles, int h) {
2
    int max = 0;
3
    for (int p : piles) max = Math.max(max, p);
4
    for (int k = 1; k <= max; k++) {
5
        long hours = 0;
6
        for (int p : piles) {
7
            // Integer ceiling — a partial pile still costs a full hour.
8
            hours += (p + k - 1) / k;   // ceil(p / k)
9
        }
10
        // First feasible k is the answer because feasibility is monotone.
11
        if (hours <= h) {
12
            return k;
13
        }
14
    }
15
    return max;
16
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.16 lines

D · Why it works and complexityO(n * max(piles)) timeO(1) spaceOpen the invariant and proofExplore the proof

The feasibility function hours(k) is monotonically non-increasing in k. Any monotone predicate over an ordered range is exactly the setting where linear scanning is wasteful and binary search shines.

ComplexityO(n * max(piles)) time, O(1) space — Up to max(piles) candidate speeds, each costing O(n) to total the hours.

E · Edge cases and pitfalls2Sweeping up to 10⁹ speeds — times out.Explore edge cases

Pitfalls

Sweeping up to 10⁹ speeds — times out.
Using floor division p // k instead of ceiling — undercounts hours for partial piles.

03.2

Approach 2 of 2 · Optimal

Binary Search on the Answer (Optimal)

TimeO(n log(max(piles)))SpaceO(1)

The answer they want. Say 'I'll binary search the speed, not the array' and justify with monotonicity.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You noticed hours(k) only goes down as k goes up. If speed k finishes in time, what do you know about every speed faster than k?

2Hint 2Explore hint

That monotonicity means the feasible speeds form a contiguous upper range. Binary search the boundary in [1, max(piles)].

3Hint 3Explore hint

For a candidate k, compute total hours = Σ⌈pile/k⌉. If ≤ h, the answer is k or smaller (hi = k); otherwise it's larger (lo = k + 1). Return lo.

A · Core idea

Binary search the speed rather than any array.

Reframing the problem. There's no sorted array to search here. What's ordered is the answer space: possible speeds 1, 2, …, max(piles). The function hours(k) = Σ ⌈piles[i] / k⌉ is monotonically non-increasing in k — eating faster never makes Koko take longer. Therefore the speeds that satisfy hours(k) <= h form a contiguous suffix [k*, max], and we want the leftmost feasible speed k*. That's a textbook boundary-finding binary search.

The bounds. The slowest meaningful speed is 1 (she must eat). The fastest useful speed is max(piles): at that speed every pile takes exactly one hour, and going faster can't reduce the per-pile cost below one hour, so it never helps. A feasible answer always exists because h >= piles.length, so k = max(piles) (one pile per hour) is guaranteed to fit.

The feasibility check. For a candidate k, sum ⌈piles[i] / k⌉. Use the integer-only ceiling (p + k - 1) / k to avoid floating-point error. In Java accumulate into a long: with up to 10⁴ piles each costing up to 10⁹ hours, an int sum overflows.

The boundary template. Use while (lo < hi) with lo = 1, hi = max(piles). Compute k = lo + (hi - lo) / 2. If hours(k) <= h, this speed works, but a slower one might too, so keep k as a candidate with hi = k. Otherwise k is too slow, so lo = k + 1. When lo == hi they point at the smallest feasible speed — return lo. Keeping mid on success (hi = k, not k - 1) is what makes this find the minimum.

Why this is fast. We replaced the linear sweep over up to 10⁹ speeds with log₂(10⁹) ≈ 30 feasibility checks. Each check is O(n), so the whole thing is O(n log(max(piles))) — instant even at the constraint limits.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

piles = [3, 6, 7, 11], h = 8

Array state

lo=1, hi=11

k=6 → 6 hrs ≤ 8 feasible → search slower

lo ↓

[0]

[1]

[2]

[3]

[4]

k ↓

[5]

[6]

[7]

[8]

[9]

hi ↓

[10]

Current pointerResolved stateNot processed

Final result4

C · Code with teaching comments

solution.javaJava

Binary Search on the Answer (Optimal) — optimal

8 teaching notes

1
public int minEatingSpeed(int[] piles, int h) {
2
    // Speed range starts at 1; hi becomes max(piles) below.
3
    int lo = 1, hi = 0;
4
    for (int p : piles) hi = Math.max(hi, p);
5
    // Boundary search for the smallest feasible speed — pairs with hi = k.
6
    while (lo < hi) {
7
        int k = lo + (hi - lo) / 2;
8
        // Monotone feasibility test: does speed k clear all piles within h hours?
9
        if (canFinish(piles, k, h)) {
10
            // k works; a slower speed might too, so keep k as a candidate.
11
            hi = k;
12
        } else {
13
            // k too slow → the answer is strictly faster.
14
            lo = k + 1;
15
        }
16
    }
17
    return lo;
18
}
19
 
20
private boolean canFinish(int[] piles, int k, int h) {
21
    // long, not int — the sum can exceed 2^31 for big inputs.
22
    long hours = 0;
23
    for (int p : piles) {
24
        // Ceiling division: a partial pile still costs a whole hour.
25
        hours += (p + k - 1) / k;   // ceil(p / k)
26
        // Early exit once we exceed h — also caps the running sum.
27
        if (hours > h) return false;
28
    }
29
    return hours <= h;
30
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.30 lines

D · Why it works and complexityO(n log(max(piles))) timeO(1) spaceOpen the invariant and proofExplore the proof

The mental move is 'binary search the answer, not the input'. Whenever a problem says minimize/maximize a number such that a check passes, test whether the check is monotone in that number; if it is, binary search the numeric range and let an O(n) feasibility function do the work. This exact pattern solves Capacity to Ship Packages Within D Days, Split Array Largest Sum, and Minimum Number of Days to Make Bouquets — only the feasibility function changes.

ComplexityO(n log(max(piles))) time, O(1) space — log₂(max(piles)) candidate speeds, each feasibility check scanning all n piles → O(n log(max(piles))). Only scalars stored → O(1) space.

E · Edge cases and pitfalls8piles = [1000000000], h = 2 — hi = 1e9; with one pile, k = ceil(1e9 / h) ≈ 5e8 — long arithmetic prevents overflow.Explore edge cases

Edge cases handled

piles = [1000000000], h = 2hi = 1e9; with one pile, k = ceil(1e9 / h) ≈ 5e8 — long arithmetic prevents overflow.
piles = [312884470], h = 312884469h huge but just shy of letting k=1 finish in one pass; binary search still finds the minimal speed.
piles = [5], h = 5k must clear 5 bananas in 5 hours → k = 1 (ceil(5/1)=5 ≤ 5).
h == piles.lengthOnly one hour per pile → answer is max(piles); the search converges to hi.

Pitfalls

int overflow on the hour sum in Java — use long.
Starting lo at 0 — speed 0 means she never finishes (division by zero too).
Floor instead of ceiling for per-pile hours.
Using hi = k - 1 on success — overshoots and may skip the true minimum.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int minEatingSpeed(int[] piles, int h) { int lo = 1, hi = 0; for (int p : piles) hi = Math.max(hi, p); while (lo < hi) { int k = lo + (hi - lo) / 2;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Floor instead of ceiling hours

A pile that isn't a clean multiple of k still consumes a full final hour. Floor division undercounts, so an infeasible speed looks feasible.

Explore the code comparison

Don't write this

hours = sum(p // k for p in piles)        # floor — wrong

Write this instead

hours = sum((p + k - 1) // k for p in piles)  # ceil

Integer overflow on the hour sum

With up to 10⁴ piles each needing up to 10⁹ hours at k=1, the running total exceeds Integer.MAX_VALUE and wraps negative, breaking the comparison.

Explore the code comparison

Don't write this

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

Write this instead

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

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Binary search on the answer (monotone feasibility)

Code pattern to memorize

lo, hi = 1, max(piles)
while lo < hi:
    k = lo + (hi - lo) // 2
    hours = sum((p + k - 1) // k for p in piles)
    if hours <= h: hi = k        # k works, try smaller
    else: lo = k + 1             # too slow, need faster
return lo

Rules to remember

1Search the answer space [1, max(piles)], not array indices — k can never exceed the biggest pile (more speed is wasted).
2Hours for one pile is the ceiling ⌈p / k⌉; compute as (p + k - 1) / k to avoid floating point.
3Feasibility is monotone: if speed k finishes in time, so does any speed > k — that monotonicity is what makes binary search valid.
4Use the while (lo < hi) + hi = k template to find the smallest feasible speed; return lo.
5Use long for the hour sum in Java — n up to 10⁴ piles of up to 10⁹ each can overflow int.

Use this pattern when

'Find the minimum/maximum value X such that a feasibility check passes' with a monotone check
The thing you're optimising isn't in the input array but in a numeric range you define
Problems phrased as 'smallest capacity / speed / time / threshold that still works'

Choose another pattern when

The feasibility predicate isn't monotone in the parameter → binary search on the answer doesn't apply
The answer range is tiny → a direct linear scan over candidates is simpler
You're searching for an element that's literally in a sorted array → that's ordinary binary search

Interview takeaway

When the answer is a number with a monotone 'does this work?' test, binary search the answer range instead of the data. Recognising that monotonicity — 'bigger always stays feasible' — is the whole unlock, and it generalises to Capacity to Ship Packages, Split Array Largest Sum, and Minimum Speed to Arrive on Time.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternBinary search on the answer with a monotone feasibility predicate. Recognise it when the prompt is 'minimize/maximize a number such that a check passes' and 'bigger always stays feasible'. Same family as Capacity to Ship Packages and Split Array Largest Sum.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Capacity To Ship Packages Within D Days
Coming soon
Binary search the ship capacity; feasibility = packing fits in D days.
Split Array Largest Sum
Coming soon
Binary search the max subarray sum; feasibility = ≤ m splits.
Minimum Number of Days to Make m Bouquets
Coming soon
Binary search on the day; feasibility = enough adjacent bloomed flowers.
Binary Search
The plain array version of the same halving idea.

Same pattern

←

Search a 2D Matrix

Continue · Next problem

Median of Two Sorted Arrays

mediumBinary SearchLC #875Frequently asked

Koko Eating Bananas

LCPractice

Binary Search · 5 of 16 · 10 min

Koko loves to eat bananas. There are n piles of bananas, the i-th pile has piles[i] bananas. The guards have gone and will come back in h hours.

Return the minimum integer k such that she can eat all the bananas within h hours.

In plain English

Examples

Example 1

Input: piles = [3, 6, 7, 11], h = 8
Output: 4
Note: At k=4: ceil(3/4)+ceil(6/4)+ceil(7/4)+ceil(11/4) = 1+2+2+3 = 8 ≤ 8. At k=3 it takes 1+2+3+4 = 10 > 8, so 4 is the minimum.

Example 2

Input: piles = [30, 11, 23, 4, 20], h = 5
Output: 30
Note: Only 5 hours for 5 piles, so each pile must be cleared in one hour → k must be at least the largest pile, 30.

Example 3

Input: piles = [30, 11, 23, 4, 20], h = 6
Output: 23
Note: With one spare hour, k=23 works: ceil values 2+1+1+1+1 = 6 ≤ 6.

Constraints

1 ≤ piles.length ≤ 10⁴
piles.length ≤ h ≤ 10⁹
1 ≤ piles[i] ≤ 10⁹

Clarifying questions4First question: Can Koko split one pile across hours or eat from multiple piles in one hour?Explore questions

Q1.Can Koko split one pile across hours or eat from multiple piles in one hour?
She eats from only one pile per hour, and a pile smaller than k still consumes the whole hour. That's why a pile costs ⌈p/k⌉ hours.
Q2.What's the valid range for k?
At least 1 (she must make progress) and at most max(piles) — any faster than that finishes each pile in one hour and adds nothing.
Q3.Is h always large enough for a solution to exist?
Yes — h ≥ piles.length, so even at the maximum useful speed (one pile per hour) she finishes, guaranteeing a feasible k exists.
Q4.How big can the numbers get — should I worry about overflow?
Yes in Java: up to 10⁴ piles, each costing up to 10⁹ hours, sums beyond int range. Use long for the hour accumulator.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you recognise a 'minimize X subject to a monotone constraint' problem and binary search the answer space, rather than only knowing binary search as 'find element in sorted array'.

Where candidates slip

Computing hours with integer division (floor) instead of ceiling, setting the search range wrong (starting at 0, or hi too small), or overflowing the hour sum in Java.

How to stand out

State the monotonicity explicitly ('faster never hurts'), justify the [1, max] bounds, and use the smallest-feasible boundary template cleanly.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Linear Scan Over Speeds (Baseline)	`O(n * max(piles))`	`O(1)`	Mention to expose the monotone feasibility idea, then replace the linear sweep with binary search.	Read
2	Binary Search on the Answer (Optimal)Optimal	`O(n log(max(piles)))`	`O(1)`	The answer they want. Say 'I'll binary search the speed, not the array' and justify with monotonicity.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Linear Scan Over Speeds (Baseline)

TimeO(n * max(piles))SpaceO(1)

Mention to expose the monotone feasibility idea, then replace the linear sweep with binary search.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

What's the slowest speed that could possibly work, and the fastest you'd ever need?

2Hint 2Explore hint

Try k = 1, 2, 3, ... and for each compute the total hours; return the first k that fits in h.

3Hint 3Explore hint

Correct, but max(piles) can be 10⁹, so sweeping every speed is far too slow — notice the hours only ever decrease as k grows.

A · Core idea

Try every speed from 1 upward; for each, sum ⌈pile / k⌉ over all piles and return the first k whose total is ≤ h.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

piles = [3, 6, 7, 11], h = 8

k=1

3+6+7+11 = 27 > 8

Statetoo slow

Final result4

C · Code with teaching comments

solution.javaJava

Linear Scan Over Speeds (Baseline) — reference

2 teaching notes

1
public int minEatingSpeed(int[] piles, int h) {
2
    int max = 0;
3
    for (int p : piles) max = Math.max(max, p);
4
    for (int k = 1; k <= max; k++) {
5
        long hours = 0;
6
        for (int p : piles) {
7
            // Integer ceiling — a partial pile still costs a full hour.
8
            hours += (p + k - 1) / k;   // ceil(p / k)
9
        }
10
        // First feasible k is the answer because feasibility is monotone.
11
        if (hours <= h) {
12
            return k;
13
        }
14
    }
15
    return max;
16
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.16 lines

D · Why it works and complexityO(n * max(piles)) timeO(1) spaceOpen the invariant and proofExplore the proof

The feasibility function hours(k) is monotonically non-increasing in k. Any monotone predicate over an ordered range is exactly the setting where linear scanning is wasteful and binary search shines.

ComplexityO(n * max(piles)) time, O(1) space — Up to max(piles) candidate speeds, each costing O(n) to total the hours.

E · Edge cases and pitfalls2Sweeping up to 10⁹ speeds — times out.Explore edge cases

Pitfalls

Sweeping up to 10⁹ speeds — times out.
Using floor division p // k instead of ceiling — undercounts hours for partial piles.

03.2

Approach 2 of 2 · Optimal

Binary Search on the Answer (Optimal)

TimeO(n log(max(piles)))SpaceO(1)

The answer they want. Say 'I'll binary search the speed, not the array' and justify with monotonicity.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You noticed hours(k) only goes down as k goes up. If speed k finishes in time, what do you know about every speed faster than k?

2Hint 2Explore hint

That monotonicity means the feasible speeds form a contiguous upper range. Binary search the boundary in [1, max(piles)].

3Hint 3Explore hint

For a candidate k, compute total hours = Σ⌈pile/k⌉. If ≤ h, the answer is k or smaller (hi = k); otherwise it's larger (lo = k + 1). Return lo.

A · Core idea

Binary search the speed rather than any array.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

piles = [3, 6, 7, 11], h = 8

Array state

lo=1, hi=11

k=6 → 6 hrs ≤ 8 feasible → search slower

lo ↓

[0]

[1]

[2]

[3]

[4]

k ↓

[5]

[6]

[7]

[8]

[9]

hi ↓

[10]

Current pointerResolved stateNot processed

Final result4

C · Code with teaching comments

solution.javaJava

Binary Search on the Answer (Optimal) — optimal

8 teaching notes

1
public int minEatingSpeed(int[] piles, int h) {
2
    // Speed range starts at 1; hi becomes max(piles) below.
3
    int lo = 1, hi = 0;
4
    for (int p : piles) hi = Math.max(hi, p);
5
    // Boundary search for the smallest feasible speed — pairs with hi = k.
6
    while (lo < hi) {
7
        int k = lo + (hi - lo) / 2;
8
        // Monotone feasibility test: does speed k clear all piles within h hours?
9
        if (canFinish(piles, k, h)) {
10
            // k works; a slower speed might too, so keep k as a candidate.
11
            hi = k;
12
        } else {
13
            // k too slow → the answer is strictly faster.
14
            lo = k + 1;
15
        }
16
    }
17
    return lo;
18
}
19
 
20
private boolean canFinish(int[] piles, int k, int h) {
21
    // long, not int — the sum can exceed 2^31 for big inputs.
22
    long hours = 0;
23
    for (int p : piles) {
24
        // Ceiling division: a partial pile still costs a whole hour.
25
        hours += (p + k - 1) / k;   // ceil(p / k)
26
        // Early exit once we exceed h — also caps the running sum.
27
        if (hours > h) return false;
28
    }
29
    return hours <= h;
30
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.30 lines

D · Why it works and complexityO(n log(max(piles))) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(n log(max(piles))) time, O(1) space — log₂(max(piles)) candidate speeds, each feasibility check scanning all n piles → O(n log(max(piles))). Only scalars stored → O(1) space.

E · Edge cases and pitfalls8piles = [1000000000], h = 2 — hi = 1e9; with one pile, k = ceil(1e9 / h) ≈ 5e8 — long arithmetic prevents overflow.Explore edge cases

Edge cases handled

piles = [1000000000], h = 2hi = 1e9; with one pile, k = ceil(1e9 / h) ≈ 5e8 — long arithmetic prevents overflow.
piles = [312884470], h = 312884469h huge but just shy of letting k=1 finish in one pass; binary search still finds the minimal speed.
piles = [5], h = 5k must clear 5 bananas in 5 hours → k = 1 (ceil(5/1)=5 ≤ 5).
h == piles.lengthOnly one hour per pile → answer is max(piles); the search converges to hi.

Pitfalls

int overflow on the hour sum in Java — use long.
Starting lo at 0 — speed 0 means she never finishes (division by zero too).
Floor instead of ceiling for per-pile hours.
Using hi = k - 1 on success — overshoots and may skip the true minimum.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int minEatingSpeed(int[] piles, int h) { int lo = 1, hi = 0; for (int p : piles) hi = Math.max(hi, p); while (lo < hi) { int k = lo + (hi - lo) / 2;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Floor instead of ceiling hours

A pile that isn't a clean multiple of k still consumes a full final hour. Floor division undercounts, so an infeasible speed looks feasible.

Explore the code comparison

Don't write this

hours = sum(p // k for p in piles)        # floor — wrong

Write this instead

hours = sum((p + k - 1) // k for p in piles)  # ceil

Integer overflow on the hour sum

With up to 10⁴ piles each needing up to 10⁹ hours at k=1, the running total exceeds Integer.MAX_VALUE and wraps negative, breaking the comparison.

Explore the code comparison

Don't write this

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

Write this instead

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

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Binary search on the answer (monotone feasibility)

Code pattern to memorize

lo, hi = 1, max(piles)
while lo < hi:
    k = lo + (hi - lo) // 2
    hours = sum((p + k - 1) // k for p in piles)
    if hours <= h: hi = k        # k works, try smaller
    else: lo = k + 1             # too slow, need faster
return lo

Rules to remember

1Search the answer space [1, max(piles)], not array indices — k can never exceed the biggest pile (more speed is wasted).
2Hours for one pile is the ceiling ⌈p / k⌉; compute as (p + k - 1) / k to avoid floating point.
3Feasibility is monotone: if speed k finishes in time, so does any speed > k — that monotonicity is what makes binary search valid.
4Use the while (lo < hi) + hi = k template to find the smallest feasible speed; return lo.
5Use long for the hour sum in Java — n up to 10⁴ piles of up to 10⁹ each can overflow int.

Use this pattern when

'Find the minimum/maximum value X such that a feasibility check passes' with a monotone check
The thing you're optimising isn't in the input array but in a numeric range you define
Problems phrased as 'smallest capacity / speed / time / threshold that still works'

Choose another pattern when

The feasibility predicate isn't monotone in the parameter → binary search on the answer doesn't apply
The answer range is tiny → a direct linear scan over candidates is simpler
You're searching for an element that's literally in a sorted array → that's ordinary binary search

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Capacity To Ship Packages Within D Days
Coming soon
Binary search the ship capacity; feasibility = packing fits in D days.
Split Array Largest Sum
Coming soon
Binary search the max subarray sum; feasibility = ≤ m splits.
Minimum Number of Days to Make m Bouquets
Coming soon
Binary search on the day; feasibility = enough adjacent bloomed flowers.
Binary Search
The plain array version of the same halving idea.

Same pattern

←

Search a 2D Matrix

Continue · Next problem

Median of Two Sorted Arrays