Koko Eating Bananas – 875. LeetCode

In the Koko Eating Bananas problem, Koko the gorilla loves bananas and is given several piles of them. Each pile has a certain number of bananas, and Koko can eat at most k bananas per hour. Given a time limit h hours, the task is to determine the minimum eating speed k such that Koko can finish all the bananas within the given time.

This problem requires balancing the speed of eating with the constraints of time, which makes it a good canidate for optimization techniques.

Brute Force Approach

public class KokoEatingBananas {
    public int minEatingSpeed(int[] piles, int h) {
        for (int speed = 1; ; speed++) {
            int totalHours = 0;
            for (int pile : piles) {
                totalHours += Math.ceil((double) pile / speed);
            }
            if (totalHours <= h) {
                return speed;
            }
        }
    }
}

• The brute force approach starts with the slowest speed, 1 banana per hour, and checks if Koko can finish all piles within h hours. It increases the speed incrementally and recalculates the total hours required until it finds a speed that satisfies the condition. This words by simulating every possivle eating speed but is computationally expensive.

Optimal Algorithm and Data Structure

Algorithm: Binary Search on Eating Speed

• Pattern Used: Binary Search

• Binary Search is ideal for problems where you need to search for an optimal value within a range, and a function can tell you if a guess is valid or not.

• If Koko eats faster, she will finish faster, and if she eats slower, it will take more time. This monotonic relationship between eating speed and time required makes it suitable for Binary Search.

• Instead of checking all speeds sequentially, Binary Search divides the possible range of speeds in half at each step, drastically reducing the number of calculations.

Steps of the Algorithm

1. Define the range of eating speeds: low = 1, high = max(piles).

2. Perform Binary Search:

• Calculate the mid-point speed.

• Check if Koko can eat all piles within h hours at this speed.

• If yes, search for slower speeds (high = mid – 1); otherwise, search for faster speeds (low = mid + 1).

3. Return the minimum speed that satisfies the condition.

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

    private boolean canFinish(int[] piles, int h, int speed) {
        int hours = Arrays.stream(piles)
                      .map(pile -> (pile + speed - 1) / speed) // Calculate hours for each pile
                      .sum(); // Sum up the hours
        return hours <= h;
    }
}    

Line By Line Description

Step 1: Define Koko’s Eating Speed Range

int left = 1, right = Arrays.stream(piles).max().getAsInt();

• Sets up the initial range for Koko’s possible eating speeds:
  • left = 1: The slowest eating speed Koko could possible have is 1 banana per hour.
  • right = max(piles): This is the fastest eating speed is the size of the largest pile.

Step 2: Perform Binary Search

while (left < right) {

• Koko is testing different eating speeds to find the slowest one that lets her finish all the bananas on time. She starts by dividing her options in half.

Step 3: Test the Midpoint Speed

int mid = left + (right - left) / 2;

• Koko picks a speed in the middle of her current range to see if it’s fast enough.

Step 4: Check If Koko Can Finish at Speed mid

if (canFinish(piles, h, mid)) {
    right = mid;
} else {
    left = mid + 1;
}

• Calls canFinish to check if Koko can eat all the bananas within h hours at speed mid.

• If she can, right is set to mid to test even slower speeds.

• If she cannot, left is set to mid + 1 to test faster speeds.

Step 5: Return The Minimum Speed

return left;

• After testing various speeds, Koko finds the slowest possible speed that still lets her finish all the bananas on time.

Step 6: Calculate Total Hours for a Given Speed

private boolean canFinish(int[] piles, int h, int speed) {
    int hours = Arrays.stream(piles)
                      .map(pile -> (pile + speed - 1) / speed)
                      .sum(); // Sum up the hours
    return hours <= h;
}

• This helper function determines whether a given speed is fast enough for Koko to finish all piles on time.
• Koko calculates how long it will take to finish all the piles at her current speed and checks if it’s within her time limit.
• We need to calculate how many full hours koko requires to eat a pile of bananas at a given speed
• If koko can eat up to speed bananas in one hour, then for a pile of size pile, the hours required to finish it are:

Why the Code Was Written This Way

• Binary Search: Efficiently narrows down the possible speeds instead of testing every single one.

• Integer Arithmetic: Avoids floating-point operations for simplicity and precision.

• Clear Bounds: Ensures that the search always converges to a valid speed.

• Readable Logic: The if-else structure cleanly separates the cases for adjusting the range.

This approach guarantees an optimal solution in logarithmic time, which is far more efficient than a brute-force search.