Koko Eating Bananas

Problem Statement

Koko eats bananas at k bananas/hour. Given piles and h hours, find the minimum integer k so she finishes all piles within h hours (each hour she eats from one pile, finishing smaller piles early).

Example

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

Approach

This is binary search on the answer. The required hours decrease as k increases (a monotone predicate). Search k in [1, max(piles)]; for each candidate compute total hours sum(ceil(pile / k)) and move toward smaller feasible k.

Complexity

• Time: O(n log max(piles))
• Space: O(1)

Solution Code

Python

import math
def minEatingSpeed(piles, h):
    left, right = 1, max(piles)
    while left < right:
        mid = (left + right) // 2
        hours = sum(math.ceil(p / mid) for p in piles)
        if hours <= h:
            right = mid
        else:
            left = mid + 1
    return left

Java

int minEatingSpeed(int[] piles, int h) {
    int left = 1, right = 0;
    for (int p : piles) right = Math.max(right, p);
    while (left < right) {
        int mid = left + (right - left) / 2;
        long hours = 0;
        for (int p : piles) hours += (p + mid - 1) / mid;   // ceil
        if (hours <= h) right = mid;
        else left = mid + 1;
    }
    return left;
}

C++

int minEatingSpeed(vector<int>& piles, int h) {
    int left = 1, right = *max_element(piles.begin(), piles.end());
    while (left < right) {
        int mid = left + (right - left) / 2;
        long long hours = 0;
        for (int p : piles) hours += (p + mid - 1) / mid;   // ceil
        if (hours <= h) right = mid;
        else left = mid + 1;
    }
    return left;
}

Key Takeaways

• Recognise the monotone predicate "can finish in h hours" to binary-search the answer.
• Ceiling division: (p + k - 1) / k in integer arithmetic.
• Reference: LeetCode 875 (Koko Eating Bananas).