algoadvance

Leetcode 875. Koko Eating Bananas

Problem Statement

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

Clarifying Questions

  1. Is it guaranteed that h is at least as large as the number of piles?
    • Yes, h is always greater than or equal to n. This means it’s always possible to finish all the bananas in the given time.
  2. What are the limits on n and h?
    • Typically, 1 <= n <= 10^4 and n <= h <= 10^9.
  3. What are the limits on the number of bananas in each pile (piles[i])?
    • 1 <= piles[i] <= 10^9.

Strategy

To solve this problem efficiently, a binary search approach is suitable because the possible values of k (bananas per hour) lie in a range that can be systematically narrowed down.

  1. Initialize Binary Search Range:
    • The minimum possible eating speed would be 1 banana per hour.
    • The maximum possible eating speed would be the pile that has the most bananas, i.e., max(piles).
  2. Binary Search Implementation:
    • Calculate the middle point of the current range as the potential eating speed k.
    • Simulate eating with speed k to check if Koko can finish all bananas in h hours.
    • Adjust search range based on whether Koko can finish eating in time:
      • If she can, try a slower speed by adjusting the upper bound.
      • If she cannot, increase the speed by adjusting the lower bound.
  3. Stopping Condition:
    • The process stops when the search range converges, giving the minimum k that allows Koko to finish all bananas in h hours.

Code

public class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int left = 1;
        int right = getMax(piles);
        
        while (left < right) {
            int mid = left + (left + right) / 2;
            if (canFinish(piles, h, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        return left;
    }

    private int getMax(int[] piles) {
        int max = 0;
        for (int pile : piles) {
            if (pile > max) {
                max = pile;
            }
        }
        return max;
    }

    private boolean canFinish(int[] piles, int h, int k) {
        int hours = 0;
        for (int pile : piles) {
            hours += Math.ceil((double)pile / k);
        }
        return hours <= h;
    }
}

Explanation

Time Complexity

This solution efficiently finds the minimum k by leveraging binary search over the possible range of eating speeds and checking feasibility in linear time for each candidate speed.

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