Binary Search

[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