algoadvance

Leetcode 875. Koko Eating Bananas

Problem Statement

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 that hour.

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

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

Clarifying Questions

  1. Can Koko eat from multiple piles in a single hour?
    • No, Koko can only choose one pile to eat from in a single hour.
  2. Does Koko rest between hours or can she start a new pile immediately after finishing one pile?
    • Koko can start a new pile immediately after finishing one. The constraint is primarily on the number of hours available to finish all piles.
  3. How should we handle edge cases where n is very large or very small?
    • Assume that n and h are within reasonable bounds for calculation on a typical machine, as per LeetCode’s constraints.

Strategy

To find the minimum integer k that allows Koko to eat all bananas within h hours, we can utilize a binary search. Given that the speed k must lie between 1 and the maximum of piles (as eating faster than the largest pile in one hour is unnecessary), we can binary search within this range to find the smallest valid k.

Steps:

  1. Define the binary search range for k, which is [1, max(piles)].
  2. Implement a helper function to determine the number of hours Koko needs to eat all bananas at a given speed k.
  3. Perform binary search:
    • Calculate the mid-value.
    • Use the helper function to check if Koko can finish in h hours or less.
    • Adjust the search range accordingly.

Time Complexity

Overall, the time complexity is O(n log(max(piles))).

Code

#include <vector>
#include <algorithm>

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

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

private:
    bool canFinish(const std::vector<int>& piles, int h, int k) {
        int hours = 0;
        for (int pile : piles) {
            hours += (pile + k - 1) / k; // ceil(pile / k)
        }
        return hours <= h;
    }
};

This solution implements the binary search approach described, with the helper function calculating the total hours needed based on a given eating speed k. The minEatingSpeed function returns the minimum speed such that Koko can eat all the bananas within h hours.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI