Leetcode 875. Koko Eating Bananas

Problem

Leetcode 875 - Koko Eating Bananas

Example:

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

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

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

Approach

We can use a binary search to solve this problem where left pointer is 1, and right pointer is max of the array ‘piles’.

We can move the pointer by calculating the hour first ($hour += math.ceil(p/mid)$) where p = every pile in piles. This will result in 2 scenarios

• hour <= h, where h is permitted hour
  • then we update the k value to mid
  • update the right pointer since we’re trying to find the minimum k such that she can eat all bananas within h hours
• hour > h,
  • then we simply update the left pointer because it takes too long to consume all bananas, Koko must eat more

Visualization of the Approach:

piles = [3,6,7,11], h = 8
left = 1, right = max(piles) = 11
mid = 6
hour = ceil(3/6) + ceil(6/6) + ceil(7/6) + ceil(11/6) = 1 + 1 + 2 + 2 = 6
Since hour <= h, update k and right
k = 6

left = 1, right = 5
mid = 3
hour = ceil(3/3) + ceil(6/3) + ceil(7/3) + ceil(11/3) = 1 + 2 + 3 + 4 = 10
Since hour > h, update left
k = 6

left = 4, right = 5
mid = 4
hour = ceil(3/4) + ceil(6/4) + ceil(7/4) + ceil(11/4) = 1 + 2 + 2 + 3 = 8
Since hour <= h, update k and right
k =  4

left = 4, right =  3
Since left > right break the loop

return k = 4

Here is the Python code for the solution:

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        left, right = 1, max(piles)
        k = 0

        while left <= right:
            mid = (left + right) // 2
            hour = 0

            for p in piles:
                hour += math.ceil(p/mid)
            
            # Koko can finish all the bananas in piles thus update k, right
            if hour <= h:
                k = mid
                right = mid - 1
            # Koko can't finish all the bananas thus update left
            else:
                left = mid + 1
        return k     
    

Time Complexity and Space Complexity

Time Complexity: $O(n log m)$ where $m$ is maximum number of bananas in pile $n$ is length of the array ‘piles’

Space Complexity: $O(1)$