Crack the Backend

Problem Statement

There are n piles of bananas; piles[i] is the number of bananas in pile i. The guards will be back in h hours. Koko can choose her eating speed k (bananas per hour). Each hour she chooses a pile and eats k bananas from it; if the pile has fewer than k, she eats all of them and does not eat from another pile that hour. Return the minimum k such that she can eat all bananas within h hours.

For a pile of size p, the hours needed at speed k is ceil(p / k). Total hours = sum over piles of ceil(piles[i] / k). We need this to be <= h. Binary search on k in [1, max(piles)].

Key Observations

Binary search on k: low = 1, high = max(piles). For mid, compute total hours = sum of ceil(piles[i] / mid) = sum of (piles[i] + mid - 1) / mid (integer). If hours <= h, mid works and we can try smaller (high = mid); else low = mid + 1.
Monotonic: if k works, any larger k also works (fewer or equal hours). So we search for the minimum k that works.

Approach

High-level: Binary search k in [1, max(piles)]. For each mid, hours = sum((p + mid - 1) / mid) for each pile p. If hours <= h, high = mid; else low = mid + 1. Return low.

Steps:

low = 1, high = max(piles). While low < high: mid = low + (high - low) / 2. hours = 0; for each p in piles, hours += (p + mid - 1) / mid. If hours <= h, high = mid; else low = mid + 1.
Return low.

Implementation

Java

public int minEatingSpeed(int[] piles, int h) {
    int low = 1, high = 0;

    for (int p : piles) {
        high = Math.max(high, p);
    }

    while (low < high) {
        int mid = low + (high - low) / 2;
        long hours = 0;

        for (int p : piles) {
            hours += (p + mid - 1) / mid;
        }

        if (hours <= h) {
            high = mid;
        }
        else {
            low = mid + 1;
        }
    }

    return low;
}

Test Cases

Example 1

Input

piles = [3,6,7,11], h = 8

Expected

4

Explanation

k=4: 1+2+2+3=8 hours.

Complexity Analysis

Time: O(n log(max)).
Space: O(1).

Follow-ups

Similar: minimum time to complete trips.