Koko Eating Bananas

Koko loves to eat bananas. There are n piles of bananas, the ith 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.

Brute Force#

Try every integer eating speed from 1 up to max(piles). For each candidate speed k, simulate the hours Koko would need and check whether it fits within h hours. The first k that works is the answer. The range of candidates can be as large as 10^9, making this approach too slow (TLE) for the given constraints.

class Solution {
public:
    int minEatingSpeed(vector<int>& piles, int h) {
        int maxPile = *max_element(piles.begin(), piles.end());

        for (int k = 1; k <= maxPile; k++) {
            int hours = 0;
            for (int pile : piles)
                hours += pile / k + (pile % k != 0);  // ceil(pile / k)

            if (hours <= h) return k;  // first valid speed is the minimum
        }
        return maxPile;
    }
};

Time Complexity: O(max(piles) × n) — TLE for large inputs
Space Complexity: O(1)

binary Search#

The key observation is that the answer space is monotonic: if speed k is sufficient to finish in h hours, then any speed greater than k is also sufficient. This monotonicity lets us binary-search over the speed range [1, max(piles)] instead of checking every value linearly. For each candidate mid-speed, the hours needed for a pile of size p is ceil(p / mid), computed without floating-point as p/mid + (p % mid != 0). If the total hours is within h, we try a smaller speed (move right boundary left); otherwise we increase the speed.

• Binary Search between 1 and max(piles).
• For a mid value k, calculate total hours needed using ceil(pile/k) for each pile.
• If total hours ≤ h, update answer and search left.
• Else, search right.

class Solution {
public:
    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;

            int hourSpent = 0;

            for(int pile: piles){
                hourSpent += pile/mid + (pile % mid != 0);
            }

            if(hourSpent <= h)
                right = mid;
            else
                left = mid +1;
        }
        return right;
    }
};

Time Complexity: O(logn)

Space Complexity: O(1)