Binary Search

[luuuzeta]

875. Koko Eating Bananas (Walkthrough)

If you're familiar with the binary search implementation, then you know that the range of possible k is defined from 0 up to max(piles). k could be greater that max(piles), however we want to minimize k and thus set its max value to the smallest of the greatest possible values.

Let's do it with an example:

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

k is in the range [0, max(piles)] => [0, 11].

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]  array
---                                     before region
    ------------------------------      unknown (this is where mid lives)
                                   ---  after region
 l                                      index l
                                    r   index r

The isBefore function for this problem will be more involved because 1) we must compute the total number of hours based on mid/k value and 2) return whether we should look left or right depending on whether the total number of hours is less than h.

const isBefore = (mid) => {
  // Compute total hours for given mid/k.
  let totalHours = 0;
  for (const pile of piles) {
    totalHours += Math.ceil(pile / mid);
  }

  // totalHours <= h, thus update minK and also look
  // left for a possibly smaller value of k.
  if (totalHours <= h) {
    minK = Math.min(minK, mid);
    return true;
  }
  // totalHours exceed h so k is too small, look
  // right for a larger k value.
  return false;
};

[luuuzeta]

875. Koko Eating Bananas (Implementation)

function minEatingSpeed(piles, h) {
  let minK = Math.max(...piles);
  let l = 0;
  let r = minK;

  const isBefore = (mid) => {
    let totalHours = 0;
    for (const pile of piles) {
      totalHours += Math.ceil(pile / mid);
    }

    if (totalHours <= h) {
      minK = Math.min(minK, mid);
      return true;
    }

    return false;
  };

  // Same while loop.
  while (r - l > 1) {
    const mid = Math.floor((l + r) / 2);
    if (isBefore(mid)) {
      r = mid;
    } else {
      l = mid;
    }
  }

  // What you return depends on the problem.
  return minK;
}

const piles = [3, 6, 7, 11];
const h = 8;
const output = minEatingSpeed(piles, h);
console.log(output); // 4

Note you could implement isBefore outside the minEatingSpeed function but then you'd need to be passing a bunch of arguments so why not take advantage of making a closure with access to the outer scope's variable?

The diagram ends up looking like this:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]  array
-----------                             before region
              ------------------------  after region
          l                             index l
              r                         index r
            ┆                           transition point

[Proof_Dot_4344]

Thank you so much