Koko Eating Bananas

NeetCode: Koko Eating Bananas · LeetCode: 875. Koko Eating Bananas · Difficulty: Medium

Koko has piles of bananas and h hours. Each hour she picks one pile and eats up to k bananas from it (if the pile has fewer, she finishes it and waits out the hour). Return the minimum integer k that lets her finish all piles within h hours.

Example

Text

Input:  piles = [1, 4, 3, 2], h = 9     Output: 2
Input:  piles = [25, 10, 23, 4], h = 4  Output: 25

The hours for a pile of p bananas at speed k is ceil(p / k). Java's integer / truncates, so the code computes it as (p + k - 1) / k. LeetCode allows piles up to 10^9, so p + k - 1 can exceed Integer.MAX_VALUE. The total hours across piles can exceed it as well. The solutions below use long for both.

Brute force: try every speed

Try k = 1, 2, 3, ... and return the first speed that fits in h.

Java

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int maxPile = 0;
        for (int p : piles) {
            maxPile = Math.max(maxPile, p);
        }
        for (int k = 1; k <= maxPile; k++) {
            long hours = 0;
            for (int p : piles) {
                hours += ((long) p + k - 1) / k;
            }
            if (hours <= h) {
                return k;
            }
        }
        return maxPile;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.minEatingSpeed(new int[] {1, 4, 3, 2}, 9));
        System.out.println(s.minEatingSpeed(new int[] {25, 10, 23, 4}, 4));
    }
}

Output

2
25

Time: O(n · max(piles)). Space: O(1).

Optimal: binary search on the speed

Hours needed only decreases as speed grows, so "does speed k work?" flips from false to true exactly once. Binary search for that boundary in [1, max(piles)]. If mid works, the answer is mid or smaller (hi = mid). Otherwise it is larger (lo = mid + 1).

Java

class Solution {
    private long hoursNeeded(int[] piles, int k) {
        long hours = 0;
        for (int p : piles) {
            hours += ((long) p + k - 1) / k;
        }
        return hours;
    }

    public int minEatingSpeed(int[] piles, int h) {
        int lo = 1;
        int hi = 0;
        for (int p : piles) {
            hi = Math.max(hi, p);
        }
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (hoursNeeded(piles, mid) <= h) {
                hi = mid; // mid works, try slower
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.minEatingSpeed(new int[] {1, 4, 3, 2}, 9));
        System.out.println(s.minEatingSpeed(new int[] {25, 10, 23, 4}, 4));
        System.out.println(s.minEatingSpeed(new int[] {1_000_000_000, 1_000_000_000}, 3));
    }
}

Output

2
25
1000000000

The last call has two piles of 10^9 and h = 3. The speed must be at least 10^9, because a smaller speed needs two hours for each pile. At speed 10^9 the total is 2 hours. A smaller speed k gives 2 * ceil(10^9 / k), which is at least 4 once k < 10^9.

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