Start practising

Koko Eating Bananas

Medium Binary Search Binary Search on Answer Space Original on LeetCode

Koko Eating Bananas is a medium binary search problem solved with the binary search on answer space pattern. The best approach, optimal (binary search on the answer), runs in O(n log max) time and O(1) space. Below are 2 approaches in Java, from brute force (try every speed) up.

Problem

There are piles of bananas. Each hour Koko picks one pile and eats up to k bananas from it; if the pile has fewer, she eats all of it and waits for the next hour. Find the smallest integer speed k that lets her finish all piles within h hours.

Examples

Example 1

Input
piles = [3, 6, 7, 11], h = 8
Output
4
Why
At speed 4 the hours are 1 + 2 + 2 + 3 = 8.

Example 2

Input
piles = [30, 11, 23, 4, 20], h = 5
Output
30
Why
With one hour per pile, k must be the biggest pile.

Constraints

  • 1 <= piles.length <= h <= 10^9
  • 1 <= piles[i] <= 10^9

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

ApproachTimeSpace
Brute force (try every speed)O(max · n)O(1)
Optimal (binary search on the answer)O(n log max)O(1)

1Brute force (try every speed)

TimeO(max · n)
SpaceO(1)

Try k = 1, 2, 3, ... and return the first speed that finishes within h hours.

  1. For k from 1 to max(piles): if hours(k) <= h, return k.
Java
class Solution {
    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++) if (hours(piles, k) <= h) return k;
        return max;
    }

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

2Optimal (binary search on the answer)

TimeO(n log max)log(max) checks, each O(n).
SpaceO(1)

Speeds from 1 to max(piles) are ordered and the check hours(k) <= h flips from false to true exactly once. Binary search for the first speed where it is true.

  1. lo = 1, hi = max(piles).
  2. If hours(mid) <= h: hi = mid, else lo = mid + 1.
  3. Return lo.
Java
class Solution {
    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;
            if (hours(piles, mid) <= h) hi = mid; else lo = mid + 1;
        }
        return lo;
    }

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

Edge cases to test

  • h equals the number of piles (answer = max pile)
  • Total hours overflow int; use long

Hints

Hint 1

If Koko finishes at speed k, she also finishes at any speed above k. So the feasible speeds form a range: binary search its lower end.

FAQ

What is the best time complexity for Koko Eating Bananas?

Optimal (binary search on the answer) runs in O(n log max) time and O(1) extra space. log(max) checks, each O(n).

Which pattern does Koko Eating Bananas use?

It is a binary search problem that uses the binary search on answer space pattern. Other problems with the same pattern: Minimum Number of Days to Make m Bouquets.

Is there a brute force solution for Koko Eating Bananas?

Yes. Brute force (try every speed) takes O(max · n) time and O(1) space. Try k = 1, 2, 3, ...

Which edge cases should I test for Koko Eating Bananas?

h equals the number of piles (answer = max pile); Total hours overflow int; use long.