Skip to main content

Binary Search

Koko Eating Bananas Solution In C++/Java/Python/JS

Problem Description:

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.
koko-eating-bananas koko-eating-bananas- Problem Description

Examples:

Input: piles = [3,6,7,11], h = 8
Output: 4
Explanation: With a speed of 4, Koko can eat all piles in exactly 8 hours.

Input: piles = [30,11,23,4,20], h = 5
Output: 30
Explanation: Koko must eat at a speed of 30 to finish all piles in 5 hours.

Input: piles = [30,11,23,4,20], h = 6
Output: 23
Explanation: A speed of 23 allows Koko to eat all piles in 6 hours.

Constraints:

1 ≤ piles.length ≤ 10⁴
piles.length ≤ h ≤ 10⁹
1 ≤ piles[i] ≤ 10⁹

Brute Force Approach

We are given an array piles where piles[i] represents the number of bananas in the ith pile.

We need to find the minimum integer k such that Koko can eat all the bananas within h hours, under the following conditions:

  • Each hour, Koko chooses one pile of bananas and eats k bananas from that pile.
  • If the pile has fewer than k bananas, she eats all of them instead and does not eat any more bananas during that hour.

Let's make some observations:

  1. What is the minimum number of bananas Koko can eat per hour?
    The smallest number of bananas Koko can eat in one hour is 1. Why? Because if she eats 0, she won't make any progress in finishing the piles, and she’ll never be able to finish them within the given hours. So, the absolute minimum she can eat per hour is 1 banana.
  2. What is the maximum number of bananas Koko can eat per hour?
    The largest number of bananas Koko might eat in one hour is equal to the size of the biggest pile. For example, if the largest pile has 11 bananas, she could eat all 11 bananas in one hour. Eating more than the largest pile doesn't make sense because she can only eat from one pile in an hour, and there won’t be more bananas to eat from that pile.

Now that we know the minimum number of bananas Koko can eat in an hour (1) and the maximum number of bananas she can eat in an hour (the size of the largest pile), we need to find the smallest number of bananas k she can eat per hour so that she finishes all the bananas within h hours.

It’s clear that k must lie between these two limits:

  • If k is smaller than 1, she won’t make progress in eating the bananas.
  • If k is larger than the size of the largest pile, it’s unnecessary because she can’t eat more than what’s in the biggest pile in one hour.

So, k must be somewhere between 1 and the size of the largest pile.

Now we can start testing k with the minimum number of bananas Koko can eat in an hour (1) and check all the possible values up to the maximum number of bananas Koko can eat in an hour (the size of the largest pile).

For each value of k, we check if Koko can eat all the bananas within h hours. If we find that she can finish all the bananas within h hours for a certain value of k, we simply return that value of k as the answer.

Why?
Because it will be the smallest number of bananas Koko needs to eat per hour to finish all the bananas within the given time, as all the values of k before it would take more than h hours to finish.

Consider the example with piles = [3, 6, 7, 11] and h = 8 (the number of hours Koko has to finish eating all bananas). We start by taking the minimum speed, which is 1, as the smallest possible speed, and the maximum speed, which is the size of the largest pile, 11, as the largest possible speed.

We then check how many hours Koko would take to finish all the bananas at each of these speeds:

  • For speed = 1, Koko would take a total of 27 hours (3 + 6 + 7 + 11), which is more than 8 hours, so it doesn't work.
  • For speed = 2, Koko would take 15 hours (2 + 3 + 4 + 6), still more than 8 hours, so it doesn't work.
  • For speed = 3, Koko would take 10 hours (1 + 2 + 3 + 4), still more than 8 hours, so it doesn't work.
  • For speed = 4, Koko would take 8 hours (1 + 2 + 2 + 3), which meets the requirement of finishing within 8 hours.

Since 4 is the first speed where Koko can finish all the bananas within the required 8 hours, it is the minimum speed required. So, the answer is 4.

Now, consider the monotonic nature of the problem: Any speed between the minimum speed (1) and 3 will not work because Koko would take more than 8 hours. However, any speed from 4 to the maximum speed (11) will allow Koko to finish all bananas within 8 hours.

Therefore, 4 is the smallest speed at which Koko can finish all the bananas in 8 hours, and we return 4 as the answer.

Let's call the smallest number of speed required to finish all bananas in h hours as ans.
Any speed between the minimum possible speed (1) and ans - 1 won't work because Koko will take more than h hours to finish all the bananas.
However, any speed from ans to the maximum possible speed (the size of the largest pile) will allow Koko to finish all the bananas within h hours.

Therefore, ans is the smallest speed at which Koko can finish all the bananas in h hours, and we return ans as the answer.

koko-eating-bananas - Brute Force Approach

But how do we check if Koko can finish all the bananas within h hours for a specific speed k?

We can follow these steps:

  1. Start with a counter and set it to 0. This counter will keep track of the total hours Koko needs to finish all the piles.
  2. For every pile of bananas:
    • Divide the number of bananas in the pile by k (since this gives the hours Koko needs to finish that pile at speed k).
    • Take the ceil value of the result because Koko cannot switch to another pile within the same hour.
    • Add this value to the counter.
  3. After processing all the piles, check the value of the counter:
    • If the counter is less than or equal to h, then Koko can finish all the bananas within h hours at speed k.
    • If the counter is greater than h, then Koko cannot finish all the bananas within h hours at that speed k.

This way, we can determine if a specific speed k allows Koko to finish on time.

💡
Try it Yourself!

Let's understand with an example:

Input: piles = [3,6,7,11], h = 8
Step-by-Step:

For k = 1:

  • counter = 0 (initialize the total hours Koko needs).
  • Pile 3: ⌈3 / 1⌉ = 3 hours → counter = 3
  • Pile 6: ⌈6 / 1⌉ = 6 hours → counter = 9
  • Pile 7: ⌈7 / 1⌉ = 7 hours → counter = 16
  • Pile 11: ⌈11 / 1⌉ = 11 hours → counter = 27
  • Total counter = 27 > h = 8
  • k = 1 does not work.

For k = 2:

  • counter = 0
  • Pile 3: ⌈3 / 2⌉ = 2 hours → counter = 2
  • Pile 6: ⌈6 / 2⌉ = 3 hours → counter = 5
  • Pile 7: ⌈7 / 2⌉ = 4 hours → counter = 9
  • Pile 11: ⌈11 / 2⌉ = 6 hours → counter = 15
  • Total counter = 15 > h = 8
  • k = 2 does not work.

For k = 3:

  • counter = 0
  • Pile 3: ⌈3 / 3⌉ = 1 hour → counter = 1
  • Pile 6: ⌈6 / 3⌉ = 2 hours → counter = 3
  • Pile 7: ⌈7 / 3⌉ = 3 hours → counter = 6
  • Pile 11: ⌈11 / 3⌉ = 4 hours → counter = 10
  • Total counter = 10 > h = 8
  • k = 3 does not work.

For k = 4:

  • counter = 0
  • Pile 3: ⌈3 / 4⌉ = 1 hour → counter = 1
  • Pile 6: ⌈6 / 4⌉ = 2 hours → counter = 3
  • Pile 7: ⌈7 / 4⌉ = 2 hours → counter = 5
  • Pile 11: ⌈11 / 4⌉ = 3 hours → counter = 8
  • Total counter = 8 ≤ h = 8
  • k = 4 works! We found the minimum k that works.

Conclusion:

  • k = 4 is the minimum number of bananas Koko should eat per hour to finish all bananas within h = 8 hours.

Steps to Implement the Solution:

Define a Function to Check Time:

  • Create a helper function canFinishInTime(piles, h, speed):
    • Input: List of piles (piles), the total allowed hours (h), and the speed (speed).
    • Output: Boolean (True if Koko can finish all piles in h hours at speed k).
    • For each pile, calculate the time required to finish the pile at speed k: ceil(pile / speed).
    • Accumulate the time for all piles. If the total time exceeds h, return False. Otherwise, return True.

Loop Through All Possible Speeds:

  • Start with the minimum speed (1).
  • Start with the maximum speed (max(piles)).
  • Loop through all speeds starting from the minimum (1) to the maximum (max(piles)).

Check Feasibility for Each Speed:

  • For each speed in the loop, call canFinishInTime(piles, h, speed).
    • If the function returns True (i.e., Koko can finish in time), then return this speed as the result. This will be the minimum speed that works, as you're checking speeds in increasing order.

Edge Handling:

  • If no valid speed is found by the time you reach the maximum pile size, return -1 (though this is unlikely due to the constraints).
Code Implementation / Leetcode solutions of koko eating bananas
1. C++ Try on Compiler 
class Solution {
    // Function to check if Koko can finish all bananas within 'h' hours at a given speed 'k'
    bool canFinishInTime(vector<int> &piles, int h, int speed) {

        // Total hours Koko will take to finish all piles
        long long totalHours = 0; 

        // Iterate through each pile and calculate how many hours Koko will take to finish each pile
        for(auto &pile : piles) {

            // Time for this pile at speed 'k'
            totalHours += ceil((double)pile / speed); 
        }

        // Return whether the total time is within the allowed hours 'h'
        return totalHours <= h;
    }

public:
    // Function to find the minimum eating speed
    int minEatingSpeed(vector<int>& piles, int h) {

        // Minimum speed Koko can eat per hour
        int minSpeed = 1; 

        // Maximum speed is the size of the largest pile
        int maxSpeed = *max_element(piles.begin(), piles.end()); 

        // Try all speeds from minSpeed to maxSpeed and check if Koko can finish in 'h' hours
        for(int speed = minSpeed; speed <= maxSpeed; speed++) {

            // If Koko can finish in time with the current speed
            if(canFinishInTime(piles, h, speed)) {

                // Return the current speed as the answer
                return speed; 
            }
        }

        // If no valid speed found, return -1 (though this shouldn't happen given the problem constraints)
        return -1;
    }
};

2. Java Try on Compiler 
class Solution {
    // Function to check if Koko can finish all bananas within 'h' hours at a given speed 'k'
    public boolean canFinishInTime(int[] piles, int h, int speed) {

        // Total hours Koko will take to finish all piles
        long totalHours = 0; 

        // Iterate through each pile and calculate how many hours Koko will take to finish each pile
        for (int pile : piles) {

            // Time for this pile at speed 'k'
            totalHours += Math.ceil((double) pile / speed); 
        }

        // Return whether the total time is within the allowed hours 'h'
        return totalHours <= h;
    }

    public int minEatingSpeed(int[] piles, int h) {

        // Minimum speed Koko can eat per hour
        int minSpeed = 1; 

        // Maximum speed is the size of the largest pile
        int maxSpeed = Arrays.stream(piles).max().getAsInt(); 

        // Try all speeds from minSpeed to maxSpeed and check if Koko can finish in 'h' hours
        for (int speed = minSpeed; speed <= maxSpeed; speed++) {

            // If Koko can finish in time with the current speed
            if (canFinishInTime(piles, h, speed)) {
                
                // Return the current speed as the answer
                return speed;
            }
        }

        // If no valid speed found, return -1 (though this shouldn't happen given the problem constraints)
        return -1;
    }
}

3. Python Try on Compiler 
import math

class Solution:
    # Function to check if Koko can finish all bananas within 'h' hours at a given speed 'k'
    def canFinishInTime(self, piles, h, speed):

        # Total hours Koko will take to finish all piles
        totalHours = 0  

        # Iterate through each pile and calculate how many hours Koko will take to finish each pile
        for pile in piles:

            # Time for this pile at speed 'k'
            totalHours += (pile + speed - 1) // speed 

        # Return whether the total time is within the allowed hours 'h'
        return totalHours <= h

    def minEatingSpeed(self, piles, h):

        # Minimum speed Koko can eat per hour
        minSpeed = 1  

        # Maximum speed is the size of the largest pile
        maxSpeed = max(piles)  

        # Try all speeds from minSpeed to maxSpeed and check if Koko can finish in 'h' hours
        for speed in range(minSpeed, maxSpeed + 1):

            # If Koko can finish in time with the current speed
            if self.canFinishInTime(piles, h, speed):
                
                # Return the current speed as the answer
                return speed

        # If no valid speed found, return -1 (though this shouldn't happen given the problem constraints)
        return -1

4. Javascript Try on Compiler 
/**
 * @param {number[]} piles
 * @param {number} h
 * @return {number}
 */
var canFinishInTime = function(piles, h, speed) {
    let totalHours = 0; // Total hours Koko will take to finish all piles

    // Iterate through each pile and calculate how many hours Koko will take to finish each pile
    for (let pile of piles) {
        totalHours += Math.ceil(pile / speed); // Time for this pile at speed 'k'
    }

    // Return whether the total time is within the allowed hours 'h'
    return totalHours <= h;
};

var minEatingSpeed = function(piles, h) {
    let minSpeed = 1; // Minimum speed Koko can eat per hour
        let maxSpeed = Math.max(...piles); // Maximum speed is the size of the largest pile

        // Try all speeds from minSpeed to maxSpeed and check if Koko can finish in 'h' hours
        for (let speed = minSpeed; speed <= maxSpeed; speed++) {

            // If Koko can finish in time with the current speed
            if (canFinishInTime(piles, h, speed)) {
                
                // Return the current speed as the answer
                return speed;
            }
        }

        // If no valid speed found, return -1 (though this shouldn't happen given the problem constraints)
        return -1;  
};

Time Complexity: O(n * max(piles))

  1. For Each Speed (Loop from minSpeed to maxSpeed):
    We are iterating over every possible speed from minSpeed (1) to maxSpeed (the largest pile in piles).
    In the worst case, this loop will run max(piles) times.
  2. For Each Pile (Inside the canFinishInTime function):
    For each speed, we call the canFinishInTime function.
    Inside this function, we iterate over each pile in the list piles to calculate the total time required for Koko to finish all the bananas at the current speed.
    This results in an O(n) complexity for each speed check, where n is the number of piles.
  3. Combining the Two:
    We loop through all possible speeds from 1 to max(piles). For each speed, we are checking if Koko can finish all bananas in the given time, which takes O(n).
    Therefore, the overall time complexity becomes: O(n * max(piles)) where n is the number of piles and max(piles) is the largest value in the piles array.

Final Time Complexity:
O(n * max(piles)) where n is the number of piles and max(piles) is the maximum number of bananas in a single pile.

Space Complexity: O(n)

  1. Auxiliary Space Complexity: O(1)
    The extra space used for variables like totalTime and speed, is constant. These are just primitive variables that occupy O(1) space.
    Therefore, the auxiliary space complexity is O(1).
  2. Total Space Complexity: O(n)
    The input consists of the piles array, which is the main data structure, and its size is O(n) where n is the number of piles.
    Therefore, the total space complexity is O(n).

Will Brute Force Work Against the Given Constraints? 

For the current solution, the time complexity is O(n * max(piles)), where n is the number of piles (with an upper limit of 10⁴), and max(piles) is the maximum number of bananas in a pile, which can be as large as 10⁹ in the worst-case scenario. This means the solution can handle up to approximately O(10⁴ * 10⁹) operations in the worst case.

However, given the constraints, the solution is not efficient enough for many typical inputs. In competitive programming environments, problems generally allow up to 10⁶ operations per test case. While the time complexity may exceed this for the worst-case scenario, most inputs will likely stay within a manageable range and execute efficiently within the given time limits.

Therefore, the O(n * max(piles)) time complexity does not guarantee that the solution will work efficiently for all input sizes within the problem's constraints. While it may perform well for typical inputs, it is crucial to consider the worst-case inputs that could push the solution beyond the upper limit. With careful optimization, it could perform well in most practical cases.

How to optimize it?

In the previous approach, we examined the minimum and maximum speeds at which Koko could eat bananas and checked every speed within that range to find the minimum speed k such that Koko could finish all the bananas within h hours. This resulted in a time complexity of O(n * max(piles)), which was too slow and caused a TLE (Time Limit Exceeded) error.

Now, let’s think about improving this.
The main issue was that we checked every speed from minimum to maximum, which took a lot of time.

Can we make this part faster?

Yes! Here’s the hint:

We are searching for the minimum speed such that Koko can finish all the bananas within h hours, and we know that this speed lies between the minimum speed (1) and the maximum speed (the size of the largest pile of bananas).

Now that we know the two endpoints, the minimum eating speed and the maximum eating speed, let's make a few observations:

  1. The search space is sorted:
    The range of speeds, from the minimum speed (1) to the maximum speed (the size of the largest pile), is naturally sorted.
  2. The search space is monotonic:
  • If a certain speed allows Koko to finish all bananas within h hours, then any larger speed will also work.
  • If a certain speed doesn’t work, then any smaller speed will also fail.
  • For the example with the piles [3, 6, 7, 11] and h = 8 hours, Koko will fail to finish all bananas within 8 hours for all speeds from 1 to 3 (F, F, F). Starting from speed 4 onwards, Koko will succeed in finishing within the required 8 hours (T, T, T, T...). This illustrates the monotonic property: once a speed works (from 4), it will continue to work for all larger speeds.
  1. The middle element helps minimize or maximize the search space:
    If we take the middle value of the current range and check if Koko can finish all the bananas within h hours, we can narrow the search space:
    If it works, we move to the left half to find a smaller valid speed.
    If it doesn’t work, we move to the right half to find a larger speed that works.

If we plot a graph with the range of speeds on the x-axis and whether Koko can finish all the bananas within h hours on the y-axis, we can observe the following:

For a given speed, Koko can either finish all bananas or not. Before the minimum speed (denoted as minSpeed), Koko cannot finish all the bananas within h hours. This is because, for any speed from the start up to minSpeed - 1, the required time to finish all the bananas exceeds h hours. From minSpeed onwards, Koko is able to finish the bananas within the required time. This is because once we reach minSpeed, the conditions are met for Koko to complete all bananas within h hours, and this condition remains valid as we move further to higher speeds. Thus, minSpeed represents the earliest speed at which Koko can finish the bananas within h hours, and from that point forward, finishing within h hours remains feasible for all higher speeds.

With these points in mind, it's clear that instead of linearly checking all values from the minimum to the maximum speed, we can take the middle value and continually reduce the search space.

koko-eating-bananas - Graph Explaination

Does this approach remind you of something you've seen before?

Yes, we are applying binary search here. By leveraging the sorted and monotonic properties of the speed range, we efficiently narrow down the search space to find the minimum speed that allows Koko to finish all the bananas within h hours, instead of checking each value linearly.

💡
How binary search works?

Binary search can help us quickly find the minimum speed by narrowing down the range in each step.

We can simply use binary search to determine the minimum eating speed Koko needs to finish all the bananas within h hours. Start by taking the middle value between the low (minimum speed) and high (maximum speed). If this mid-value satisfies the condition that Koko can finish all the bananas within h hours, we store it as a potential answer and narrow the search space to the left half, looking for a smaller speed. Otherwise, we move the search to the right half to find a larger valid speed. We continue this process as long as low <= high.

Once the condition breaks, the stored answer is returned as the minimum speed.

By using binary search, we can cut the search space in half at each step, which makes the solution much faster and avoids the TLE issue.

💡
Try it Yourself!

Let's understand with an example:

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

Initial Setup:

  • low = 1 (minimum speed)
  • high = 11 (maximum speed, size of largest pile)

First iteration:

  • mid = (low + high) / 2 = (1 + 11) / 2 = 6
  • Check if Koko can finish all bananas at speed 6 within 8 hours:
    • For pile 3: ceil(3/6) = 1
    • For pile 6: ceil(6/6) = 1
    • For pile 7: ceil(7/6) = 2
    • For pile 11: ceil(11/6) = 2
    • Total hours = 1 + 1 + 2 + 2 = 6 hours (which is <= 8)
  • Since it works, store 6 as a potential answer and adjust high = mid - 1 = 5.

Second iteration:

  • low = 1, high = 5
  • mid = (low + high) / 2 = (1 + 5) / 2 = 3
  • Check if Koko can finish all bananas at speed 3 within 8 hours:
    • For pile 3: ceil(3/3) = 1
    • For pile 6: ceil(6/3) = 2
    • For pile 7: ceil(7/3) = 3
    • For pile 11: ceil(11/3) = 4
    • Total hours = 1 + 2 + 3 + 4 = 10 hours (which is > 8)
  • Since it doesn’t work, adjust low = mid + 1 = 4.

Third iteration:

  • low = 4, high = 5
  • mid = (low + high) / 2 = (4 + 5) / 2 = 4
  • Check if Koko can finish all bananas at speed 4 within 8 hours:
    • For pile 3: ceil(3/4) = 1
    • For pile 6: ceil(6/4) = 2
    • For pile 7: ceil(7/4) = 2
    • For pile 11: ceil(11/4) = 3
    • Total hours = 1 + 2 + 2 + 3 = 8 hours (which is <= 8)
  • Since it works, store 4 as a potential answer and adjust high = mid - 1 = 3.

End Condition:

  • low = 4, high = 3 (the loop ends)
  • The minimum valid speed found is 4, so the answer is 4.
0:00
/3:48

koko-eating-bananas - Optimal Animation

How to code it up:

  1. Helper Function (canFinishInTime)
  • Purpose: Check if Koko can finish all bananas in h hours at a given speed.
  • Steps:
    • Initialize totalHours to 0.
    • For each pile, calculate hours using ceil(pile / speed) and add to totalHours.
    • Return totalHours <= h.
  1. Main Function (minEatingSpeed)
  • Purpose: Find the minimum speed for Koko to finish all bananas in h hours.
  • Steps:
    • Set minSpeed = 1 and maxSpeed = max(piles).
    • Perform binary search:
      • While minSpeed <= maxSpeed:
        • Set midSpeed.
        • If canFinishInTime(piles, h, midSpeed) is true:
          • Set result = midSpeed and maxSpeed = midSpeed - 1.
        • Otherwise, set minSpeed = midSpeed + 1.
    • Return result.
Code Implementation / Leetcode solutions of koko eating bananas
1. C++ Try on Compiler 
class Solution {
    // Function to check if Koko can finish all bananas within 'h' hours at a given speed 'k'
    bool canFinishInTime(vector<int> &piles, int h, int speed) {

        // Variable to store the total hours Koko will take to finish all piles
        long long totalHours = 0; 

        // Iterate through each pile and calculate how many hours Koko will take to finish each pile
        for (auto &pile : piles) {

            // Time required to finish this pile at the current speed
            totalHours += ceil((double)pile / speed); 
        }

        // Return whether the total time is within the allowed hours 'h'
        return totalHours <= h;
    }

public:
    // Function to find the minimum eating speed using binary search
    int minEatingSpeed(vector<int>& piles, int h) {

        // Minimum speed Koko can eat per hour (1 banana per hour is the lowest possible speed)
        int minSpeed = 1; 

        // Maximum speed is the size of the largest pile (this would be the worst-case maximum speed)
        int maxSpeed = *max_element(piles.begin(), piles.end()); 

        // Variable to store the final answer for the minimum eating speed
        int result = 0;

        // Perform binary search between minSpeed and maxSpeed
        while (minSpeed <= maxSpeed) {

            // Calculate the middle speed to check
            int midSpeed = minSpeed + (maxSpeed - minSpeed) / 2;

            // If Koko can finish all bananas within 'h' hours at this speed, try to lower the speed
            if (canFinishInTime(piles, h, midSpeed)) {

                // Update the result with the current speed
                result = midSpeed;  

                // Narrow down the search space to smaller speeds
                maxSpeed = midSpeed - 1;  
            }
            else {
                
                // Narrow down the search space to larger speeds
                minSpeed = midSpeed + 1;  
            }
        }

        // Return the minimum speed at which Koko can finish all bananas within 'h' hours
        return result;
    }
};

2. Java Try on Compiler 
class Solution {
    // Function to check if Koko can finish all bananas within 'h' hours at a given speed 'k'
    public boolean canFinishInTime(int[] piles, int h, int speed) {
        long totalHours = 0;

        // Iterate through each pile and calculate how many hours Koko will take to finish each pile
        for (int pile : piles) {
            totalHours += Math.ceil((double) pile / speed);
        }

        // Return whether the total time is within the allowed hours 'h'
        return totalHours <= h;
    }

    // Function to find the minimum eating speed using binary search
    public int minEatingSpeed(int[] piles, int h) {
        // Minimum speed Koko can eat per hour (1 banana per hour is the lowest possible speed)
        int minSpeed = 1;

        // Maximum speed is the size of the largest pile
        int maxSpeed = 0;
        for (int pile : piles) {
            maxSpeed = Math.max(maxSpeed, pile);
        }

        // Variable to store the final answer for the minimum eating speed
        int result = 0;

        // Perform binary search between minSpeed and maxSpeed
        while (minSpeed <= maxSpeed) {

            // Calculate the middle speed to check
            int midSpeed = minSpeed + (maxSpeed - minSpeed) / 2;

            // If Koko can finish all bananas within 'h' hours at this speed, try to lower the speed
            if (canFinishInTime(piles, h, midSpeed)) {

                // Update the result with the current speed
                result = midSpeed;  

                // Narrow down the search space to smaller speeds
                maxSpeed = midSpeed - 1;  
            } else {

                // Narrow down the search space to larger speeds
                minSpeed = midSpeed + 1;  
            }
        }

        // Return the minimum speed at which Koko can finish all bananas within 'h' hours
        return result;
    }
}

3. Python Try on Compiler 
import math

class Solution:
    # Function to check if Koko can finish all bananas within 'h' hours at a given speed 'k'
    def canFinishInTime(self, piles, h, speed):
        totalHours = 0

        # Iterate through each pile and calculate how many hours Koko will take to finish each pile
        for pile in piles:
            totalHours += (pile + speed - 1) // speed

        # Return whether the total time is within the allowed hours 'h'
        return totalHours <= h

    # Function to find the minimum eating speed using binary search
    def minEatingSpeed(self, piles, h):
        # Minimum speed Koko can eat per hour (1 banana per hour is the lowest possible speed)
        minSpeed = 1

        # Maximum speed is the size of the largest pile
        maxSpeed = max(piles)

        # Variable to store the final answer for the minimum eating speed
        result = 0

        # Perform binary search between minSpeed and maxSpeed
        while minSpeed <= maxSpeed:
            # Calculate the middle speed to check
            midSpeed = minSpeed + (maxSpeed - minSpeed) // 2

            # If Koko can finish all bananas within 'h' hours at this speed, try to lower the speed
            if self.canFinishInTime(piles, h, midSpeed):

                # Update the result with the current speed
                result = midSpeed  

                # Narrow down the search space to smaller speeds
                maxSpeed = midSpeed - 1  
            else:

                # Narrow down the search space to larger speeds
                minSpeed = midSpeed + 1  

        # Return the minimum speed at which Koko can finish all bananas within 'h' hours
        return result

4. Javascript Try on Compiler 
/**
 * @param {number[]} piles
 * @param {number} h
 * @return {number}
 */
var canFinishInTime = function (piles, h, speed) {
    let totalHours = 0; // Total hours Koko will take to finish all piles

    // Iterate through each pile and calculate how many hours Koko will take to finish each pile
    for (let pile of piles) {
        totalHours += Math.ceil(pile / speed); // Time for this pile at speed 'k'
    }

    // Return whether the total time is within the allowed hours 'h'
    return totalHours <= h;
};

var minEatingSpeed = function (piles, h) {

    // Minimum speed Koko can eat per hour (1 banana per hour is the lowest possible speed)
    let minSpeed = 1;

    // Maximum speed is the size of the largest pile
    let maxSpeed = Math.max(...piles);

    // Variable to store the final answer for the minimum eating speed
    let result = 0;

    // Perform binary search between minSpeed and maxSpeed
    while (minSpeed <= maxSpeed) {
        
        // Calculate the middle speed to check
        let midSpeed = minSpeed + Math.floor((maxSpeed - minSpeed) / 2);

        // If Koko can finish all bananas within 'h' hours at this speed, try to lower the speed
        if (canFinishInTime(piles, h, midSpeed)) {

            // Update the result with the current speed
            result = midSpeed;  

            // Narrow down the search space to smaller speeds
            maxSpeed = midSpeed - 1;  
        } else {

            // Narrow down the search space to larger speeds
            minSpeed = midSpeed + 1;  
        }
    }

    // Return the minimum speed at which Koko can finish all bananas within 'h' hours
    return result;
};

Time Complexity: O(n * log(max(piles)))

  1. Binary Search Loop: The binary search loop runs on the range between minSpeed and maxSpeed.
    In each iteration, the search space is halved. Therefore, the number of iterations is proportional to the logarithm of the difference between maxSpeed and minSpeed.
    The maximum value of maxSpeed is the size of the largest pile, so the number of binary search iterations is O(log(max(piles))).
  2. Checking Feasibility for Each Speed (canFinishInTime function):
    For each mid-speed value during the binary search, we need to check whether Koko can finish the bananas within the given time h.
    This is done by iterating through all the piles to calculate the total time required for the given speed. This step takes O(n) time, where n is the number of piles.

Overall Time Complexity:
The binary search loop runs O(log(max(piles))) times.
Each time, we check the feasibility of a certain speed, which takes O(n) time.
Therefore, the overall time complexity is: O(n * log(max(piles))).

Space Complexity: O(n)

  1. Auxiliary Space Complexity: O(1)
    The space complexity is O(1) because we only use a constant amount of extra space (apart from the input data).
  2. Total Space Complexity: O(n)
    The input array piles takes O(n) space, where n is the number of piles.
    Therefore, the total space complexity is O(n).

Similar Problems

Now we have successfully tackled this problem, let's try these similar problems.

1. Binary Search

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.You must write an algorithm with O(log n) runtime complexity.

2. Sqrt(x)

Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.You must not use any built-in exponent function or operator.For example, do not use pow(x, 0.5) in C++ or x ** 0.5 in Python.

💡
Showcase your skills by joining LearnYard Technologies FZ-LLC as a Technical Content Writer. Apply now and inspire the next generation of learners—fill out the form: https://forms.gle/CGDsbGkcapSfvXKM8