🐒

KOKO eating Bananas

Prerequisites: 🍦Binary Search(Vanilla) , 🔑Find the First True in a Sorted Boolean Array ,🧩Monotonic function, 🛖Ceiling(Upper Bound)

QUESTION

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.

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

LEETCODE

REFRAMING THE QUESTION

Each hour, Koko chooses some pile of bananas, And from that pile Eats bananas with a speed of k bananas per hour.

If the pile has fewer than the k bananas, she eats them all and remains idle for the rest of the hour.
If the pile has more than k bananas, she will eat k bananas and continue with the same pile for the next hour.

speed(k) = 5 | pile = 6 bananas —> takes 2 hours.

Let us try some speeds. With a pile of 3 bananas, see how many hours she takes.

We can conclude generally,

If we eat slowly, it will take us longer to finish.
If we eat too quickly, we might overeat and have to wait idly afterwards.

Returning the minimum integer k such that she can eat all the bananas within h hours. This means we have to return a speed k that is not slow enough, that we exceed the allotted time, or too quick that we eat all the bananas and we are waiting idly for a long period before the guard comes back💂🏻.

What are the relevant speeds? Let's look at the piles in the example above and determine the least and most speed possible.

Piles

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

Let’s calculate the number of hours it takes Koko to finish all the piles at different speeds (k).

The Quicker the monkey eats the less time it takes.

In the context of the question above, what is the quickest and slowest speed possible for Koko?

The quickest speed that will be relevant is equal to the pile with the most bananas. This is because if she tries to eat them with a speed of 11, she will be able to eat all the bananas in 4 hours. If she tries to eat them at a speed of 15, it will still take the same amount of time to finish all the piles; the only difference is that she will be waiting idly for longer in between hours.

The image above Koko eating bananas with 11 bananas each hour

What will her slowest speed be? That's simple enough: one banana per hour. She can't do worse than that. We could say 0.5 bananas, but the question asks us to return an integer, so we take whole values.

Since we have reframed our understanding with different examples let's go and build the intuition for this question.

Brute force Intuition

We are trying to get the minimum speed at which KOKO can eat all the bananas before the guard comes back.

We start to check values from the slowest speed of 1 to the maximum number of piles,
The first value where we are able to eat all the bananas allowed will be the speed that is our minimum integer k such that she can eat all the bananas within h hours? Why is that?

All the values before it are slower, so we won't be able to eat within the allotted time. These values are unfeasible.
All the values after this are sufficient to consume the bananas within the allotted time. However, for quicker speeds we might eat too quickly and have to wait idealy. These values are feasible.

As we increase our speed, from 1 to 2 to 3, the time it takes to consume the piles decreases. The relationship between speed and time is a monotonic function.

Since nature is monotonic and decreasing. When we reach the first speed where we can eat all the bananas in the allotted time, all subsequent speeds will also allow us to do so but will be faster. And all the values before that are such that they are too slow. Therefore, the first speed at which we can eat all the bananas in the allotted time will be the optimal speed—Not too slow not too fast.

Iteration (Code)

Iterating over the range of possible values.

least,most = 1,max(piles)
for speed in range(least,most+1):

Feasibility (CODE)

Calculate the total hours spent eating bananas at each speed, to check the feasibility of that speed.

The simple way

res = float("inf")
least,most = 1,max(piles)
for speed in range(least,most+1):
#________________________________#
    totalHours = 0
    for p in piles:

    # each hour she can only feast on one pile.
    # koko eats the bananas for that hour from one pile and can't go to the next pile

        # eat the perfect divisible number of bananas i.e 11 with speed 3 11//3 = 3 hours

        hoursToEatPile = p//speed

        # if there are leftovers bananas left after eating the 
				# perfect divisible number of bananas 11%3, 2 bananas 
				# left will take an extra hour to eat

        hoursToEatPile += 1 if p%speed else 0 

        totalHours += hoursToEatPile
#________________________________#

The pythonic way—if there is a simple way there is always a simpler pythonic way

for speed in range(least,most+1):
#________________________________#
  totalHours = 0
  for p in pile
      
      hoursToEatPile = math.ceil(p/speed) # rounding up to include koko's down time after finishing the bananas
      totalHours += hoursToEatPile
#________________________________#

If the find a value of totalHours that is equal to or less than the hours given to us we simply return that speed.

allPilesEatenWithInTheGivenTime = totalHours <= h
if allPilesEatenWithInTheGivenTime:
    return speed

Final code

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        
        least,most = 1,max(piles)
        for speed in range(least,most+1):
            totalHours = 0
            for p in piles:


                # eat the perfect divisible number of bananas i.e 11 with speed 3 11//3 = 3 hours

                hoursToEatPile = p//speed

                # if there are leftovers bananas left after eating the perfect divisible number of bananas 11%3 = 2 bananas left will take an extra hour to eat

                hoursToEatPile += 1 if p%speed else 0 

                totalHours += hoursToEatPile

            allPilesEatenWithInTheGivenTime = totalHours <= h
            if allPilesEatenWithInTheGivenTime:
                return speed

Complexities

Time Complexity: O(N*M)

N = max(Piles)

M = len(Piles)

Space Complexity: O(1)

If you look, we are using a nested for loop here. The outer loop iterates over all the possible speeds from 1 to max(piles). With each iteration of that loop, we go over the whole piles array to check the feasibility of that speed. In the worst case, we might have to check all possible speeds until we get a possible answer. Is there a way to do better?

Logarithmic Intuition 2.0

In Part One, we checked every possible speed in a linear fashion until we reached the threshold of h hours (where it is possible to eat all the bananas within the given time), which was our value to return.

The value of time taken to speed is decreasing continuously—representing a decreasing 🧩Monotonic function.

When we reach the first speed, where we can eat all the bananas within the allotted time. All subsequent speeds will be faster than the previous one, but still, allow us to eat all the bananas. As we keep increasing speeds, we will never be in a situation where we don't have enough time to eat bananas before the guard comes back.

This will divide our space between a feasible and nonfeasible split. As we talked about in the previous part.

Instead of checking every possible value linearly. Can we try picking a random speed and try to shorten the range based on what we know about the above function?

Let's start by Picking 7 randomly

With a speed of 7, it takes 5 hours to eat all the bananas that are within the allotted time(8 hours). For values greater than 7, we can still finish the bananas quickly but at a quicker speed.

Since we are looking for the minimum speed the slowest speed might be at 7(store it as a possible) or at slower speed—to the left.
We can disregard all the values after 7. We can disregard seven as well if we store it as a possible speed.

Let’s pick another speed of 2

With a speed of 2, it takes 15 hours to eat all the bananas which is not enough time to finish all the bananas. For values less than 2, the speed will still not be enough.

The value where we can at least finish all the bananas is for sure at a faster speed than 2—to the right.
We can disregard all the values before and including 2.

The possible range now lies between 3 and 6. In two iterations, we reduced the size of the array from 11 to 4, saving us the complexity of five iterations (compared to brute force).
If we consider our minimum integer (speed) k as a border.

All values on the right including it are possible values(can eat the bananas in the allotted time).
All values before it are non-possible values (can’t eat bananas in the allotted time).

If we regard the border as the first feasible value we can reduce the problem to 🔑Find the First True in a Sorted Boolean Array

BruteForce to Optimized

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
    
        least,most = 1,max(piles)
        minSpeed = -1
        
        
        while least <= most:
            
            speed = least + (most-least)//2 
            
         # Feasibility-- Will convert this part into a separate function for more clarity
         #_____________________________________________________________________________
            totalHours = 0
            for p in piles:

      

                # eat the perfect divisible number of bananas i.e 11 with speed 3 11//3 = 3 hours
                hoursToEatPile = p//speed

                # if there are leftovers bananas left after eating the perfect 
                # divisable number of bananas 11%3 = 2 bananas left will take an extra hour to eat
                hoursToEatPile += 1 if p%speed else 0 

                totalHours += hoursToEatPile

        
            allPilesEatenWithInTheGivenTime = totalHours <= h
        #_____________________________________________________________________________
            
            # True
            if allPilesEatenWithInTheGivenTime: 

                # reduceSpeed
                minSpeed = speed
                most = speed-1
            
            #False
            else: 
                #increase speed
                least = speed + 1
               
                
                
        return minSpeed

Code 🔑Find the First True in a Sorted Boolean Array

class Solution:

    def firstTrue(self, bools):

        (left, right) = (0, len(bools) - 1)
        possibleValue = -1

        while left <= right:

            mid = left + (right - left) // 2
						
					# True
            if bools[mid]: 
                possibleValue = mid
                right = mid - 1
						
					# False
            else:
                left = mid + 1

        return possibleValue

Code for this question

class Solution:
    
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
    
        least,most = 1,max(piles) # <-- change here (left=least,right = most)
        minSpeed = -1
       
        while least <= most:
            
            speed = least + (most-least)//2 # <-- change speed instead of mid
            
            # True
            if self.allPilesEatenWithInTheGivenTime(speed,piles,h): # <-- change here
                
                minSpeed = speed
                most = speed - 1 # reduceSpeed
            #False
            else: 
                least = speed + 1 #increase speed
              
                
        return minSpeed
    
    
    
    def allPilesEatenWithInTheGivenTime(self,speed,piles,h): # <-- change here
   
         #___________________________________________________
            totalHours = 0
            for p in piles:
                hoursToEatPile = p//speed
                hoursToEatPile += 1 if p%speed else 0 
                totalHours += hoursToEatPile
            allPilesEatenWithInTheGivenTime = totalHours <= h
        #_____________________________________________________
         
            return allPilesEatenWithInTheGivenTime

Sandbox—PythonTutor (Visualized)

Time Complexity

`O(M * log(N)) N =` `max(Pile)`

N = max(Piles)

M = len(Piles)

Complexities

Time Complexity: O(M * log(N))

N = max(Pile)

M = len(Piles)

Space Complexity: O(1)

The feasibility function still needs to iterate over M times, but we can reduce the number of times we need to check for the optimal value from n to log(n).

📐Understanding Time Complexity of OLog(N): Math + Intuition

Take Away 🥡

🍦Binary Search(Vanilla) is used to find an index in an array in logarithmic time, we solved Koko's problem of eating bananas in logarithmic time without using an array. As we were able to reframe the problem into halves and how they related to the target. Don't limit your thinking to binary search when you only have an array to search. Binary search is much more versatile; just consider the monotonic (always increasing or decreasing) nature of things. In the next part, we will look at similar questions to this and see what patterns we can look to find and solve these problems.

Comparison