LC 875. Koko Eating Bananas

The problem

Solution - $O(n \log(m))$ Time

The first thing to realize with this problem is that the rates of eating that should be considered is bounded by the slowest Koko could possibly go, 1, and the fastest rate that matters which is the maximum pile. If Koko likes to eat slowly, then it doesn't make since to consider 21 bananas per hour in a case where the maximum is 20 bananas. Beyond that, eating any faster just hurts the solution as only one pile can be focused on per hour anyway.

With this in mind, we just need an efficient way to search for a rate that optimizes Koko's eating speed with the constraint of taking as long as possible to finish within the limit. Binary search will be efficient since the rate could be anything between the bounds. At a rate, midSpeed which is the midpoint of the search, the total time it will take to eat all piles will be:

Across each pile, sum the Math.ceil of however long it takes her to eat all the bananas. Those special brackets just mean Math.ceil, which captures the part of the problem that states whenever Koko finishes eating, she will wait until the next hour before moving to a new pile. Then minSpeed and maxSpeed can be shifted like normal as the left and right pointers for the binary search. If midSpeedHoursToEat is greater than h, the right maxSpeed is shifted below the current minSpeed to check slower rates.

One caveat is that instead of storing the min in its own variable, I use left to approximate it and return that at the end. However, this introduces an edge case where the right pointer, maxSpeed is shifted just beyond the answer. To handle that, the while loop includes the last case where left is equal to right (minSpeed === maxSpeed). Technically, the minSpeed will get shifted above maxSpeed at that point to give the correct answer. An example of this right pointer below the answer case is where piles = [30,11,23,4,20], h = 6. The pointers evolve like this throughout the loop where the second iteration moves the right pointer below the answer and the last row shows left moving past it to provide the solution:

function minEatingSpeed(piles: number[], h: number): number {
  let minSpeed = 1
  let maxSpeed = Math.max(...piles)

  while (minSpeed <= maxSpeed) {
    let midSpeed = Math.floor((minSpeed + maxSpeed) / 2)
    let midSpeedHoursToEat = 0
    for (const pile of piles) {
      midSpeedHoursToEat += Math.ceil(pile / midSpeed)
    }

    if (midSpeedHoursToEat > h) {
      minSpeed = midSpeed + 1
    } else {
      maxSpeed = midSpeed - 1
    }
  }

  return minSpeed
}

The last thing to note is that the time complexity is caused by looping through each element when calculating midSpeedHoursToEat which is $O(n)$ and the binary search through rates which is $O(\log m)$ hence the $O(n \log(m))$.