NeetCode 150: Koko Eating Bananas

Table of contents

The Problem

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

Koko likes to eat slowly but still wants 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.

The Approach

The goal is to determine the optimal value for k. Since it is stated that piles.length <= h <= 109, it means that the largest possible value of h is the value of the largest element in piles[i] & the smallest possible value is 1.

To optimize the search between these two values, we then apply Binary Search to locate this value.

My Solution

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int biggestPile = findAndReturnBiggestPile(piles);

        int maxBound = biggestPile;
        int minBound = 1;
        int k = 0;
        
        // Utilize a Binary Search approach to consider the possible values for k. Since
        // the possible values are sorted (1 to max), Binary Search assists in cutting
        // down the number of comparisons.
        while (maxBound >= minBound) {
            int midValue = (int) Math.ceil((maxBound + minBound) / 2.0);

            // Get the total number of hours for this k value.
            int totalHoursToEatThePile = 0;
            for (int i = 0; i < piles.length; i++) {
                totalHoursToEatThePile += (int) Math.ceil((double) piles[i] / midValue);
            }

            // If the total hours is <= h, search for a better value (i.e try a smaller midValue).
            if (totalHoursToEatThePile <= h) {
                k = midValue;
                maxBound = midValue - 1;

            // Else, this means that ideal k value has to be greater (i.e try a greater midValue). 
            } else {
                minBound = midValue + 1;
            }
        }
        return k;
    }


    // Returns the max value in the array.
    private int findAndReturnBiggestPile(int[] piles) {
        int max = 0;
        for (int i = 0; i < piles.length; i++) {
            if (piles[i] > max) {
                max = piles[i];
            }
        }
        return max;
    }
}

We first find the largest value in piles[i] using findAndReturnBiggestPile(). We then initialize l & r, which store the minimum & maximum values of k.

For each iteration of the loop, we determine the midValue & calculate the totalHoursToEatThePile using this value. This value is then compared to h & there are two outcomes:

• If totalHoursToEatThePile <= h: Koko is able to eat the entire pile. Update kValue & search for a better (i.e smaller) value for k. Shift r (i.e max value) to midValue - 1.
• If totalHoursToEatThePile > h: Koko is unable to eat the entire pile, the ideal value for kValue must be greater. Shift l (i.e min value) to midValue + 1.

At the end of the Binary Search, kValue is returned.