25. Koko Eating Bananas · DSA Practice

There are piles[i] bananas in each pile. Each hour Koko picks one pile and eats up to k bananas from it (if the pile has fewer, she finishes it and waits for the hour to end). Return the minimum integer speed k that lets her finish everything within h hours.

Example 1

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

Output: 4

Explanation: At speed 4 she needs 1 + 2 + 2 + 3 = 8 hours.

Example 2

Input: piles = [5,9,2], h = 5

Output: 5

Hint 1

If speed k works, any faster speed also works: the answer space is monotonic.

Hint 2

Binary-search the speed between 1 and max(piles).

Binary Search on Answer

Approach 1: Try every speed

Increase k from 1 until it fits.

⏱ Time O(max · n)💾 Space O(1)

Approach 2: Binary search on the answer ✅

Feasibility is monotonic in k, so binary-search the smallest feasible k.

⏱ Time O(n log max)💾 Space O(1)

Reference solution for Binary search on the answer (time O(n log max), space O(1)). Each solution passes every test in all four languages.

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        def hours(k):
            return sum((p + k - 1) // k for p in piles)    # ceil(p / k) per pile
        lo, hi = 1, max(piles)
        while lo < hi:                                     # first k with hours(k) <= h
            mid = (lo + hi) // 2
            if hours(mid) <= h:
                hi = mid
            else:
                lo = mid + 1
        return lo

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) {                       // first k that finishes in time
            int mid = lo + (hi - lo) / 2;
            long hours = 0;
            for (int p : piles) hours += (p + (long)mid - 1) / mid;
            if (hours <= h) hi = mid; else lo = mid + 1;
        }
        return lo;
    }
}

class Solution {
public:
    int minEatingSpeed(vector<int>& piles, int h) {
        int lo = 1, hi = *max_element(piles.begin(), piles.end());
        while (lo < hi) {                       // first k that finishes in time
            int mid = lo + (hi - lo) / 2;
            long long hours = 0;
            for (int p : piles) hours += (p + (long long)mid - 1) / mid;
            if (hours <= h) hi = mid; else lo = mid + 1;
        }
        return lo;
    }
};

function minEatingSpeed(piles, h) {
  let lo = 1, hi = Math.max(...piles);
  while (lo < hi) { // first k that finishes in time
    const mid = Math.floor((lo + hi) / 2);
    let hours = 0;
    for (const p of piles) hours += Math.ceil(p / mid);
    if (hours <= h) hi = mid; else lo = mid + 1;
  }
  return lo;
}

Try solving it yourself first. Interviewers care more about how you explain the approach than about the finished code.

Watch the core idea of this problem step by step. Change the input and press Visualize.

Explained in the lesson Binary Search.