Jobs

Interviews

Discussions

Koko Eating Bananas

Medium

Amazon

9 views

Topics:

ArraysBinary Search

Koko loves to eat bananas. There are n piles of bananas, the i^th 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.

Example 1:

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

Example 2:

Input: piles = [30,11,23,4,20], h = 5
Output: 30

Example 3:

Input: piles = [30,11,23,4,20], h = 6
Output: 23

Constraints:

1 <= piles.length <= 10⁴
piles.length <= h <= 10⁹
1 <= piles[i] <= 10⁹

Koko Eating Bananas

Medium

Amazon

9 views

Topics:

ArraysBinary Search

Koko loves to eat bananas. There are n piles of bananas, the i^th pile has piles[i] bananas. The guards have gone and will come back in h hours.

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.

Example 1:

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

Example 2:

Input: piles = [30,11,23,4,20], h = 5
Output: 30

Example 3:

Input: piles = [30,11,23,4,20], h = 6
Output: 23

Constraints:

1 <= piles.length <= 10⁴
piles.length <= h <= 10⁹
1 <= piles[i] <= 10⁹

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the upper and lower bounds for the values in the `piles` array, and for the number of hours `h`?
Can `piles` be empty or null? What should I return in that case?
Is it guaranteed that a valid `k` always exists that allows Koko to eat all bananas within `h` hours?
If there are multiple possible values of `k` that satisfy the condition, should I return the absolute minimum, or is any valid `k` acceptable?
Are the values in the `piles` array integers only, or could they be floating-point numbers?

Brute Force Solution

Approach

The goal is to find the slowest eating speed Koko needs to eat all the bananas within a set time. The brute force method involves trying every possible eating speed, one by one, starting from the slowest possible, until we find the smallest speed that works.

Here's how the algorithm would work step-by-step:

Start with the slowest possible eating speed: one banana per hour.
Check if Koko can eat all the bananas within the given time using this speed.
If she can, then remember this speed as a possible answer.
If not, increase the eating speed by one (e.g., two bananas per hour).
Keep checking if Koko can finish all the bananas within the time limit using this new speed.
Repeat the process of increasing the eating speed and checking if it works.
Continue until you find an eating speed that works within the time, and any slower speed does not. The current speed will be the solution.

Code Implementation

def koko_eating_bananas_brute_force(piles, hours_allowed):

    slowest_eating_speed = 1
    while True:
        total_hours_needed = 0

        # Iterate through each pile of bananas
        for pile in piles:
            total_hours_needed += (pile + slowest_eating_speed - 1) // slowest_eating_speed

        # Check if Koko can eat all bananas within the time limit
        if total_hours_needed <= hours_allowed:
            # If Koko can, then we return the eating speed, since we're checking from slowest to fastest
            return slowest_eating_speed

        # If Koko can't, increment the eating speed
        slowest_eating_speed += 1

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n * m) – The algorithm iterates through potential eating speeds, starting from 1. Let n be the number of piles of bananas and let m be the maximum number of bananas in a single pile. The maximum possible eating speed needed is thus m. For each potential eating speed, it iterates through all n piles to calculate the total time needed to eat all the bananas at that speed. Therefore, the outer loop runs up to m times, and the inner loop to check each speed runs n times, making the time complexity O(n * m).

Space Complexity

O(1) – The brute force algorithm described iteratively checks eating speeds, updating only a few variables like the current eating speed and a flag indicating whether the current speed is feasible. It doesn't utilize any auxiliary data structures (like arrays or hash maps) to store intermediate results or track visited states. Therefore, the space required remains constant irrespective of the number of banana piles. The auxiliary space complexity is O(1).

Optimal Solution

Approach

The core idea is to use a process of elimination to find the best eating speed for Koko. Instead of trying every possible speed, we narrow down the possibilities by checking if a speed is too slow or too fast, using a method similar to guessing a number between 1 and 100.

Here's how the algorithm would work step-by-step:

Figure out the slowest and fastest possible eating speeds for Koko. The slowest is eating one banana per hour, and the fastest is eating all the bananas from the largest pile in one hour.
Pick a speed in the middle of the slowest and fastest speeds to test. This is your 'guess'.
Calculate how long it would take Koko to eat all the bananas at that speed.
If it takes too long (more than the time given), that means the speed is too slow, so you need to consider only faster speeds in the next step.
If it doesn't take too long, the speed might be okay, but maybe there's an even slower speed that works. So, consider only slower speeds in the next step.
Repeat steps 2-5, each time narrowing down the range of possible speeds, until you find the slowest speed that allows Koko to eat all the bananas within the given time.

Code Implementation

def koko_eating_bananas(piles, hours_to_eat):    max_pile_size = max(piles)
    left = 1
    right = max_pile_size

    while left < right:
        eating_speed = (left + right) // 2

        # Calculate how long it takes to eat all piles at this speed.
        total_time_to_eat = 0
        for pile_size in piles:
            total_time_to_eat += (pile_size + eating_speed - 1) // eating_speed

        # If it takes too long, the speed is too slow.
        if total_time_to_eat > hours_to_eat:
            left = eating_speed + 1

        # The speed is fast enough, try a slower speed.
        else:
            right = eating_speed

    # 'left' will be the minimum eating speed to finish in time.
    return left

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n log m) – The algorithm uses binary search to find the optimal eating speed. The search space for the eating speed ranges from 1 to the maximum number of bananas in a pile, where 'm' represents the maximum number of bananas in any pile. For each potential eating speed within the binary search, the algorithm iterates through the 'n' piles of bananas to calculate the total time it takes Koko to eat all the bananas. This iteration to calculate the time takes O(n) time. Since binary search takes O(log m) and within each check we take O(n) to calculate the time, the overall time complexity is O(n log m).

Space Complexity

O(1) – The algorithm predominantly uses a binary search approach which primarily involves arithmetic calculations and comparisons using a few variables to store the low, high and mid values of the search space. These variables take up constant space. There is no auxiliary data structure (like an array or hash map) that scales with the input size (number of piles of bananas). Therefore, the auxiliary space complexity is constant.

Edge Cases

Case	How to Handle
piles is null or empty	Return 0 or throw an IllegalArgumentException as there are no bananas to eat, or return an impossible rate like Integer.MAX_VALUE indicating no solution.
h is less than the number of piles	Return -1 or Integer.MAX_VALUE, indicating that it is impossible to eat all bananas within the given time, since Koko can only eat from one pile per hour.
piles contains only one pile	Calculate the minimum k directly by dividing the number of bananas in the pile by h, ceiling the result, and return that.
All piles have a small number of bananas (e.g., 1 or 2)	The binary search will quickly converge to a rate of 1 or 2, handled correctly by the `hoursNeeded` calculation.
One pile has a huge amount of bananas (potential for integer overflow in calculation of hours)	Use long type for intermediate calculations of hours needed, especially when dividing pile size by rate.
piles contains very large values leading to potential integer overflow when calculating hours	Ensure calculations for total hours use long data type to prevent overflow and provide accurate results.
h is a very large number (e.g., greater than the sum of the pile sizes)	The binary search lower bound should be 1, and upper bound should be the max pile size; the binary search will converge to the smallest possible rate.
All piles are the same size	The binary search will efficiently converge to the correct rate, as the `hoursNeeded` calculation will be consistent across iterations.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the upper and lower bounds for the values in the `piles` array, and for the number of hours `h`?
Can `piles` be empty or null? What should I return in that case?
Is it guaranteed that a valid `k` always exists that allows Koko to eat all bananas within `h` hours?
If there are multiple possible values of `k` that satisfy the condition, should I return the absolute minimum, or is any valid `k` acceptable?
Are the values in the `piles` array integers only, or could they be floating-point numbers?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start with the slowest possible eating speed: one banana per hour.
Check if Koko can eat all the bananas within the given time using this speed.
If she can, then remember this speed as a possible answer.
If not, increase the eating speed by one (e.g., two bananas per hour).
Keep checking if Koko can finish all the bananas within the time limit using this new speed.
Repeat the process of increasing the eating speed and checking if it works.
Continue until you find an eating speed that works within the time, and any slower speed does not. The current speed will be the solution.

Code Implementation

def koko_eating_bananas_brute_force(piles, hours_allowed):

    slowest_eating_speed = 1
    while True:
        total_hours_needed = 0

        # Iterate through each pile of bananas
        for pile in piles:
            total_hours_needed += (pile + slowest_eating_speed - 1) // slowest_eating_speed

        # Check if Koko can eat all bananas within the time limit
        if total_hours_needed <= hours_allowed:
            # If Koko can, then we return the eating speed, since we're checking from slowest to fastest
            return slowest_eating_speed

        # If Koko can't, increment the eating speed
        slowest_eating_speed += 1

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Figure out the slowest and fastest possible eating speeds for Koko. The slowest is eating one banana per hour, and the fastest is eating all the bananas from the largest pile in one hour.
Pick a speed in the middle of the slowest and fastest speeds to test. This is your 'guess'.
Calculate how long it would take Koko to eat all the bananas at that speed.
If it takes too long (more than the time given), that means the speed is too slow, so you need to consider only faster speeds in the next step.
If it doesn't take too long, the speed might be okay, but maybe there's an even slower speed that works. So, consider only slower speeds in the next step.
Repeat steps 2-5, each time narrowing down the range of possible speeds, until you find the slowest speed that allows Koko to eat all the bananas within the given time.

Code Implementation

def koko_eating_bananas(piles, hours_to_eat):    max_pile_size = max(piles)
    left = 1
    right = max_pile_size

    while left < right:
        eating_speed = (left + right) // 2

        # Calculate how long it takes to eat all piles at this speed.
        total_time_to_eat = 0
        for pile_size in piles:
            total_time_to_eat += (pile_size + eating_speed - 1) // eating_speed

        # If it takes too long, the speed is too slow.
        if total_time_to_eat > hours_to_eat:
            left = eating_speed + 1

        # The speed is fast enough, try a slower speed.
        else:
            right = eating_speed

    # 'left' will be the minimum eating speed to finish in time.
    return left

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
piles is null or empty	Return 0 or throw an IllegalArgumentException as there are no bananas to eat, or return an impossible rate like Integer.MAX_VALUE indicating no solution.
h is less than the number of piles	Return -1 or Integer.MAX_VALUE, indicating that it is impossible to eat all bananas within the given time, since Koko can only eat from one pile per hour.
piles contains only one pile	Calculate the minimum k directly by dividing the number of bananas in the pile by h, ceiling the result, and return that.
All piles have a small number of bananas (e.g., 1 or 2)	The binary search will quickly converge to a rate of 1 or 2, handled correctly by the `hoursNeeded` calculation.
One pile has a huge amount of bananas (potential for integer overflow in calculation of hours)	Use long type for intermediate calculations of hours needed, especially when dividing pile size by rate.
piles contains very large values leading to potential integer overflow when calculating hours	Ensure calculations for total hours use long data type to prevent overflow and provide accurate results.
h is a very large number (e.g., greater than the sum of the pile sizes)	The binary search lower bound should be 1, and upper bound should be the max pile size; the binary search will converge to the smallest possible rate.
All piles are the same size	The binary search will efficiently converge to the correct rate, as the `hoursNeeded` calculation will be consistent across iterations.