☕ DSA Java Articles

Topics › Binary Search › BS on Answers

Koko eating bananas

Medium TUF ID 94 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Koko has n piles of bananas; pile i holds piles[i] bananas. The guards return in h hours. Koko picks an eating speed k (bananas per hour) and sticks to it. Each hour she chooses one pile and eats k bananas from it; if the pile has fewer than k left she finishes the pile and eats nothing else during that hour. She never switches piles mid-hour. Return the minimum integer speed k that lets her eat every banana within h hours.

Constraints: 1 ≤ n ≤ 10^4, n ≤ h ≤ 10^9, 1 ≤ piles[i] ≤ 10^9.

Example 1

piles = [3, 6, 7, 11], h = 8
answer = 4          // hours: ceil(3/4) + ceil(6/4) + ceil(7/4) + ceil(11/4) = 1 + 2 + 2 + 3 = 8

Example 2

piles = [30, 11, 23, 4, 20], h = 5
answer = 30         // h == n, so every pile must be finished in exactly one hour; the biggest pile dictates k

The feasibility check

Whatever approach we use, we need to answer one question quickly: at speed k, how many hours does Koko need? A pile of p bananas takes ceil(p / k) hours because she eats k per hour and the last hour may be partial. Summing over all piles gives the total.

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

Two details: (p + k - 1) / k is the standard integer formula for ceil(p / k) when both are positive; and the sum is a long because with 10^4 piles of 10^9 bananas and k = 1 the total is 10^13, far beyond int. The cast (long) p also keeps p + k - 1 from overflowing when p and k are both near 10^9.

Approach 1: Brute force, try every speed

Intuition. The speed never needs to exceed the largest pile: at k = max(piles) every pile takes exactly one hour, which is the fewest hours possible (n ≤ h guarantees that this always fits). So the candidate speeds are 1, 2, ..., max. Faster eating never needs more hours, so the first speed (from the slow end) that fits in h hours is the minimum.

Algorithm.

  1. Compute max = max(piles).
  2. For k = 1, 2, ..., max: if hoursNeeded(piles, k) ≤ h, return k.
  3. Return max (never reached when n ≤ h).
static int bruteForce(int[] piles, int h) {
    int max = 0;
    for (int p : piles) max = Math.max(max, p);
    for (int k = 1; k <= max; k++) {
        if (hoursNeeded(piles, k) <= h) return k;
    }
    return max;
}

Complexity. Time O(n * max): up to 10^9 speeds, each costing an O(n) scan. Space O(1). Hopeless for the given limits, but it states the idea we are about to speed up: the answer is the first k for which a monotonic predicate becomes true.

Approach 2: Optimal, binary search on the speed

Intuition. Define fits(k) = hoursNeeded(piles, k) ≤ h. If Koko can finish at speed k, she can also finish at any faster speed, because every ceil(p / k) term can only shrink when k grows. So over k = 1, 2, ..., max the predicate looks like F F F ... F T T T ... T, and we want the first T. That is a textbook binary search over the answer space, not over the array:

Algorithm.

  1. Compute max = max(piles); set lo = 1, hi = max, ans = max.
  2. While lo ≤ hi:
    • mid = lo + (hi - lo) / 2.
    • If hoursNeeded(piles, mid) ≤ h: ans = mid, hi = mid - 1.
    • Else: lo = mid + 1.
  3. Return ans.
static int optimal(int[] piles, int h) {
    int max = 0;
    for (int p : piles) max = Math.max(max, p);
    int lo = 1, hi = max, ans = max;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (hoursNeeded(piles, mid) <= h) { ans = mid; hi = mid - 1; }
        else lo = mid + 1;
    }
    return ans;
}

Dry run on piles = [3, 6, 7, 11], h = 8:

lo hi mid hours at mid fits? ans next range
1 11 6 1 + 1 + 2 + 2 = 6 yes 6 [1, 5]
1 5 3 1 + 2 + 3 + 4 = 10 no 6 [4, 5]
4 5 4 1 + 2 + 2 + 3 = 8 yes 4 [4, 3] stop

Result 4.

Complexity. Time O(n log max): about log2(10^9) ≈ 30 iterations, each an O(n) scan, so roughly 3 * 10^5 operations. Space O(1).

Why is the initial ans = max safe? Because fits(max) is always true (n hours, and n ≤ h), so if the loop somehow never records a value the fallback is still a valid answer. In practice the first mid that fits overwrites it.

The general recipe

This problem is the template for the entire “binary search on answers” section, so it is worth stating the recipe explicitly:

  1. Identify the quantity you are asked to minimise or maximise (here, speed k).
  2. Find its possible range ([1, max(piles)]).
  3. Write a feasibility function that decides, for a fixed candidate, whether the constraints hold (hoursNeeded(k) ≤ h).
  4. Argue that feasibility is monotonic in the candidate (faster is never worse).
  5. Binary search for the boundary, remembering the best feasible candidate seen.

Whenever steps 3 and 4 are possible, the search costs O(log(range)) feasibility checks regardless of how large the range is.

Edge cases and pitfalls