Koko Eating Bananas

Problem Description

Koko loves to eat bananas. There are n piles of bananas, the i-th pile has piles[i] bananas. The guards have gone and will come back in h hours.

Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour.

Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.

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

Examples

Constraints

• 1 <= piles.length <= 10⁴
• piles.length <= h <= 10⁹
• 1 <= piles[i] <= 10⁹

Binary Search on Answer Space

The eating speed k must reside in the range [1, max(piles)]. Instead of scanning every possible speed, we can use binary search on this answer range. We set left = 1 and right = max(piles). At each step, calculate the midpoint speed mid. Compute the total hours needed to finish all piles at speed mid using: hours_needed = sum(ceil(pile / mid)).

• If hours_needed <= h, mid is a valid speed. We record it as a candidate and attempt to find a slower speed by searching the left half: right = mid - 1.
• If hours_needed > h, mid is too slow, so we must search the right half: left = mid + 1.

Solution 1: Binary Search on Speed Range

Perform binary search over the possible eating speeds, validating hour totals.

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int left = 1;
        int right = 0;
        for (int pile : piles) {
            right = Math.max(right, pile); // speed upper bound
        }

        int result = right;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (canEatAll(piles, mid, h)) {
                result = mid; // record candidate
                right = mid - 1; // try slower speeds
            } else {
                left = mid + 1; // try faster speeds
            }
        }
        return result;
    }

    private boolean canEatAll(int[] piles, int speed, int h) {
        long totalHours = 0;
        for (int pile : piles) {
            // Equivalent to ceil(pile / speed) without floating-point math
            totalHours += (pile + speed - 1) / speed;
        }
        return totalHours <= h;
    }
}

class Solution:
    def minEatingSpeed(self, piles: list[int], h: int) -> int:
        left = 1
        right = max(piles)
        result = right
        
        def can_eat_all(speed: int) -> bool:
            total_hours = 0
            for pile in piles:
                # Equivalent to ceil(pile / speed)
                total_hours += (pile + speed - 1) // speed
            return total_hours <= h

        while left <= right:
            mid = left + (right - left) // 2
            if can_eat_all(mid):
                result = mid  # record candidate
                right = mid - 1  # try slower
            else:
                left = mid + 1  # try faster
                
        return result

#include <vector>
#include <algorithm>

class Solution {
private:
    bool canEatAll(const std::vector<int>& piles, int speed, int h) {
        long long totalHours = 0;
        for (int pile : piles) {
            totalHours += (pile + speed - 1) / speed;
        }
        return totalHours <= h;
    }

public:
    int minEatingSpeed(std::vector<int>& piles, int h) {
        int left = 1;
        int right = *std::max_element(piles.begin(), piles.end());
        int result = right;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (canEatAll(piles, mid, h)) {
                result = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return result;
    }
};

Complexity Analysis

• Time Complexity: O(n log m) where n is the number of piles and m is the maximum bananas count in a pile. The binary search takes log m steps, and each validation pass takes O(n) time.
• Space Complexity: O(1) auxiliary space as the search parameters are computed in place.

Where It Breaks

If h is very large (e.g. much larger than the total bananas), Koko can eat at speed 1. If h < piles.length, it is impossible to finish all piles, but the problem constraints ensure h >= piles.length.

Common Mistakes

• Integer Overflow: Using 32-bit integers to accumulate totalHours. If piles[i] is up to 10^9 and speed is small, the summation can overflow standard 32-bit registers. Using long in Java/C++ avoids this.
• Ceiling Division Bug: Using simple division pile / speed instead of ceiling division. For example, if a pile has 5 bananas and speed is 3, Koko takes 2 hours to finish it (not 1.66 or 1). Use (pile + speed - 1) / speed to compute the integer ceil directly.

Frequently Asked Questions

Why does Koko take a full hour even if the pile has fewer than k bananas? The rules state that she cannot move to another pile during the same hour, so she spends the rest of the hour resting.

Why does binary search work here? Because the relation between speed and hours is monotonic: as speed increases, the total hours needed to finish all bananas strictly decreases.

← All Problems