🌱 Keegan's Digital Garden

875. Koko Eating Bananas

2 min read

📝 Problem Details

Ref: https://neetcode.io/solutions/koko-eating-bananas

💡 Explanation of Solution

  • Observations:

    • The slowest speed Koko can eat is 1 banana per hour.
    • The fastest speed Koko needs is max(piles), since if there’s only 1 hour, she must eat the largest pile in one go.
    • The problem can be framed as a decision problem: “Is a given eating speed k feasible within h hours?”

  • Binary Search Approach:

    • Use binary search on the possible values of k (from 1 to max(piles)).
    • For a middle value k, check if it allows finishing all bananas within h hours.
    • If k is feasible (i.e., Koko can finish in ≤ h hours), try smaller values (high = k - 1).
    • If k is too slow, try larger values (low = k + 1).
    • The final answer is the smallest k that works.

  • Checking Feasibility:

    • For each pile piles[i], the time required to eat it is ceil(piles[i] / k).
    • Sum up the total hours required for all piles.
    • If total hours ≤ h, the speed k is valid.

⌛ Complexity Analysis

Time Complexity: O(n log max(piles))
	- binary search: the search space ranges from 1 to max(piles) so the binary search is O(log max(piles)) iterations
	- summing up hours for all piles takes O(n)

Space Complexity: O(1)

💻 Implementation of Solution

class Solution {
public:
    int minEatingSpeed(vector<int>& piles, int h) {
        int n = piles.size();
 
        int low = 1;
        int high = 0;
 
        for(int i=0; i<n; i++){
            high = max(high, piles[i]);
        }
 
        int result = high;
 
        while(low <= high){
            int k = low + (high - low) / 2;
            long int hours = 0;
            for(int i=0; i<n; i++){
                hours += ceil((double)piles[i]/k);
            }
            if(hours <= h){
                result = min(result, k);
                high = k - 1;
            } else {
                low = k + 1;
            }
        }
 
        return result;
    }
};

Graph View