KOKO eating Bananas

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

QUESTION

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

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

REFRAMING THE QUESTION

1. Each hour, Koko chooses some pile of bananas, And from that pile Eats bananas with a speed of k bananas per hour.
1. If the pile has fewer than the k bananas, she eats them all and remains idle for the rest of the hour.
2. If the pile has more than k bananas, she will eat k bananas and continue with the same pile for the next hour.
1. speed(k) = 5 | pile = 6 bananas —> takes 2 hours.
2. Let us try some speeds. With a pile of 3 bananas, see how many hours she takes.
1. We can conclude generally,

1. If we eat slowly, it will take us longer to finish.
2. If we eat too quickly, we might overeat and have to wait idly afterwards.
2. 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💂🏻.
3. What are the relevant speeds? Let's look at the piles in the example above and determine the least and most speed possible.
1. Piles
Copy

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


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

3. The Quicker the monkey eats the less time it takes.

4. In the context of the question above, what is the quickest and slowest speed possible for Koko?
1. 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

2. 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.
5. Since we have reframed our understanding with different examples let's go and build the intuition for this question.

Brute force Intuition

1. We are trying to get the minimum speed at which KOKO can eat all the bananas before the guard comes back.
1. We start to check values from the slowest speed of 1 to the maximum number of piles,
2. 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?
1. All the values before it are slower, so we won't be able to eat within the allotted time. These values are unfeasible.
2. 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.

3. 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.
1. 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)

1. Iterating over the range of possible values.
Copy

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

Feasibility (CODE)

1. Calculate the total hours spent eating bananas at each speed, to check the feasibility of that speed.
1. The simple way
Copy

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
#________________________________#

2. The pythonic way—if there is a simple way there is always a simpler pythonic way
Copy

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
#________________________________#

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

allPilesEatenWithInTheGivenTime = totalHours <= h
if allPilesEatenWithInTheGivenTime:
    return speed

3. Final code
Copy

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

1. 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.

2. The value of time taken to speed is decreasing continuously—representing a decreasing 🧩Monotonic function.
1. 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.

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

4. 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?
1. Let's start by Picking 7 randomly

1. 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.
1. 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.
2. We can disregard all the values after 7. We can disregard seven as well if we store it as a possible speed.

2. Let’s pick another speed of 2

3. 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.
1. The value where we can at least finish all the bananas is for sure at a faster speed than 2—to the right.
2. We can disregard all the values before and including 2.

5. 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).
6. If we consider our minimum integer (speed) k  as a border.
1. All values on the right including it are possible values(can eat the bananas in the allotted time).
2. All values before it are non-possible values (can’t eat bananas in the allotted time).
7. 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

Copy

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

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

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

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.

Similar Questions ⭐

A list of similar questions, what is the common link among them?

1. 1011. Capacity To Ship Packages Within D Days
1. least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within days days
2. 1482. Minimum Number of Days to Make m Bouquets
1. the minimum number of days you need to wait to be able to make m bouquets from the garden
3. 1231. Divide Chocolate( Leetcode Premium ) | Lintcode
1. Find the maximum total sweetness of the piece you can get by cutting the chocolate bar optimally
4. 1891. Cutting Ribbons (Leetcode Premium)
1.  the maximum possible positive integer length that you can obtain k ribbons of, or 0 if you cannot obtain k ribbons of the same length
5. 1283. Find the Smallest Divisor Given a Threshold
1. nearest integer greater than or equal to that element
6. 2141. Maximum Running Time of N Computers
1. Return the maximum number of minutes you can run all the n computers simultaneously

1. These questions will ask you to find a possible minimum or maximum given a certain threshold, such as finding the minimum time in which Koko can eat all the bananas before the guard comes back in 🐒KOKO eating Bananas , the values of x and y will have a Pas de deux along a Monotonic function. The criteria might be around.
1. Distance/speed/length
2. Time/days
3. Sum/integer/Capacity…
2. After determining that we are looking for a certain value in a monotonic function, the x (domain) values are still infinite. To reduce the possible values, we can determine the least and most values:
1. What is the least value possible? This will be our left/least value.
2. What is the most value possible? This will be our right/most valuable.
3. The nature of this question mostly follows a pattern where
Copy

least,most = max(array),sum(array) 


3. The feasibility(Different in each question) what values of y meet(above or below a certain threshold, like can she can eat all the bananas within h hours in 🐒KOKO eating Bananas
1. In 🍦Binary Search(Vanilla) We usually check linear feasibility by comparing numbers in an array to a certain target. However, this situation is different because we are checking the feasibility of a complex function. We are looking for values of x and how they meet certain criteria at y. Furthermore, we need to understand how values greater or lower than the target can be helpful in moving closer to the target.
4. The values of y are monotonic. We can optimize the unfeasible and feasible split due to the nature of the question.
1. Solutions on one side of the border will be feasible, and those on the other side unfeasible. The border marks the minimum or maximum value, which is the answer we seek.
2. We are looking for the minimum value. It will be the first feasible (true) value, where all values before it is infeasible (false) solutions.
1. In the case of 🐒KOKO eating Bananas , Small values were infeasible, while large values were feasible. If we are on the feasible side, the answer lies to the left; conversely, if we are on the infeasible side, the answer lies to the right, similar to 🛖Ceiling(Upper Bound)

3. To find the maximum value, search for the last feasible solution (True) in a range from feasible solutions (True) to unfeasible solutions (False).
1. In the case of ⬜SQRT(X)—Square Root Estimation, Small values were feasible, and large values were unfeasible. If we are on the feasible side, the answer might be to the right; conversely, if we are on the unfeasible side, the answer might be to the left, 🎢Floor (Lower Bound) .

5. After accounting for the feasibility of each value, the problem reduces to optimizing the unfeasible and feasible split, reducing the problem to 🔑Find the First True in a Sorted Boolean Array or the last. Done in logarithmic time
6. Bonus Tips:
1. This framework is just a tool; it is up to you how you use it to reframe the problem.
2. Try to wrap all the feasibility code into a function, so you can separate the optimizing and feasibility components.

Comparison

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 
            
            # True
            if self.allPilesEatenWithInTheGivenTime(speed,piles,h): 
                
                minSpeed = speed
                most = speed - 1 # reduceSpeed
            
						#False
            else: 
                least = speed + 1 #increase speed
              
                
        return minSpeed
    
    
    
    def allPilesEatenWithInTheGivenTime(self,speed,piles,h): 
   
         #_____________________________________________________________________________
            totalHours = 0
            for p in piles:
                hoursToEatPile = p//speed
                hoursToEatPile += 1 if p%speed else 0 
                totalHours += hoursToEatPile
            allPilesEatenWithInTheGivenTime = totalHours <= h
        #_____________________________________________________________________________
         
            return allPilesEatenWithInTheGivenTime

class Solution:

    def shipWithinDays(self, weights: List[int], days: int) -> int:
				# least = can atleast carry the heaviest weigth
				# most = any capacity above the total weight of packages will be a waste. 
        least,most = max(weights),sum(weights)
        minCapacity = -1
       
        while least <= most:
            
            capacity = least + (most-least)//2 
            
            # True
            if self.allPackagesShippedInTime(capacity,weights,days):
                
                minCapacity = capacity
                most = capacity - 1 # shipped in time, reduce towards a better weight
            
						#False
            else: 
                least = capacity + 1 # can't ship in time, increase capacity
              
                
        return minCapacity
    
    
    
    def allPackagesShippedInTime(self,weight,weights,days):  
   
         #_____________________________________________________________________________
            totalDays = 1
            totalWeightShip = 0
            
            for w in weights:
                
                totalWeightShip+=w
                
                shipWentOverCapacity = totalWeightShip > weight
                
                if shipWentOverCapacity:
                    totalDays+=1
                    # start with a new ship with weight
                    #not accomodated in the previous ship
                    totalWeightShip = w
                
                
            
            allPackagesShippedInTime = totalDays <= days # <-- different Criteria
        #_____________________________________________________________________________
         
            return allPackagesShippedInTime

Taking a step further…

In the next chapter, we will tackle some more difficult problems. We will be either minimizing or maximizing the smallest or largest value (minimum or maximum). I didn't understand it the first time either. We will go into more detail about reframing the problem in the next chapter.

#Double-whammy #Optimization-Squared

Some Questions

1. 410. Split Array Largest Sum
1. Return the minimized largest sum of the
2. Allocate a minimum number of pages(Geeks For Geeks)
1. Assign books in such a way that the maximum number of pages assigned to a student is minimum.
3. 848 Minimize Max Distance to Gas Station (Leetcode premium)
1. the maximum distance between adjacent gas stations is minimized

Dedication—This question is dedicated to these gentlemen who made a difficult task less difficult!

These resources cover what has been discussed and more. They can be a great starting point for your journey into learning about binary search.