150NeetCode 150

30.Koko Eating Bananas

MediumBinary Search · 3/7
LeetCode #875Video

Problem

There are n piles of bananas; pile i has piles[i] bananas. The guards return in h hours. Koko picks an eating speed k (bananas per hour). Each hour she chooses one pile and eats k bananas from it; if the pile has fewer than k bananas she finishes it and does not move to another pile that hour.

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

Examples

Input:  piles = [3, 6, 7, 11], h = 8
Output: 4
Explanation: At k = 4 the piles take 1 + 2 + 2 + 3 = 8 hours. At k = 3 they take 1 + 2 + 3 + 4 = 10 > 8.
Input:  piles = [30, 11, 23, 4, 20], h = 5
Output: 30
Explanation: With only 5 hours for 5 piles, each pile must be finished in one hour, so k must be at least the largest pile.
Input:  piles = [30, 11, 23, 4, 20], h = 6
Output: 23

Constraints

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

💡 Key Insight

The time needed, hours(k) = Σ ceil(piles[i] / k), only goes down as k goes up. So the speeds split into a "too slow" prefix and a "fast enough" suffix: F F F F T T T .... We want the first T, which is exactly what binary search on the answer finds. The answer lies in [1, max(piles)] because at speed max(piles) every pile takes one hour and h >= n.

Brute Force

TimeO(n · M) where M = max(piles)SpaceO(1).

Intuition

Try every speed k = 1, 2, 3, ... and return the first one whose total hours fit in h. It is guaranteed to stop by k = max(piles).

Algorithm

  1. Let maxPile = max(piles).
  2. For k from 1 to maxPile:
    • Compute hours = Σ ceil(p / k).
    • If hours <= h, return k.
  3. Return maxPile (unreachable in practice).

Visualization

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

k=1: 3+6+7+11 = 27 > 8 ✗
k=2: 2+3+4+6  = 15 > 8 ✗
k=3: 1+2+3+4  = 10 > 8 ✗
k=4: 1+2+2+3  =  8 ≤ 8 ✓ → return 4

Code

java
class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int maxPile = 0;
        for (int p : piles) {
            maxPile = Math.max(maxPile, p);
        }
        for (int k = 1; k <= maxPile; k++) {
            if (hoursNeeded(piles, k) <= h) {
                return k; // first speed that works is the minimum
            }
        }
        return maxPile;
    }

    private long hoursNeeded(int[] piles, int k) {
        long hours = 0; // can exceed int range when k is small
        for (int p : piles) {
            hours += (p + (long) k - 1) / k; // ceil(p / k)
        }
        return hours;
    }
}

Complexity

  • Time: O(n · M) where M = max(piles) — up to 10^9 speeds, each costing O(n). Times out.
  • Space: O(1).

Complexity Comparison

Approach Time Space
Brute Force O(n · M) O(1)
Linear Scan from Lower Bound O(n · M) worst case O(1)
Binary Search on Answer O(n · log M) O(1)

Common Pitfalls

  • Summing hours in an int — with k = 1 and huge piles the total reaches ~10^13 and overflows, making a too-slow speed look valid.
  • Using p / k instead of a ceiling: a pile of 7 at speed 4 takes 2 hours, not 1. Use (p + k - 1) / k (with a long to be safe) or Math.ceil.
  • Starting lo at 0 — mid can then be 0 and cause division by zero.
  • Mixing templates: with while (lo < hi) you must use hi = mid (not mid - 1), otherwise you can skip over the answer.
  • Setting hi = sum(piles) or 10^9 works but is wasteful; max(piles) is the tight upper bound.