12 May 2024•TypeScript•Medium

Maximize Area of Square Hole in Grid

Binary search on the side length of the square holes while counting rails removed along each axis.

View original LeetCode question

This write-up documents how I solved the LeetCode problem that asks for the largest square hole that can be carved out of a grid after removing a subset of horizontal and vertical bars. The key is to sort the removed bars and measure the longest consecutive runs along each axis.

Once we have those runs, the answer is simply the square of one plus the minimum run length because the hole must have the same side length in both dimensions.

Decision points

  • Sort the removed horizontal bars and determine the widest gap to understand how tall the hole can be.
  • Do the same for vertical bars to find the widest possible width.
  • The square side length is the minimum of those two maxima plus one (accounting for grid boundaries).

Complexity

Sorting dominates the runtime at O(n log n), where n is the number of removed bars. We only traverse the sorted arrays twice afterwards.

Source

You can view the accompanying solution file or the original problem statement for finer details:

Solution files

TypeScript•maximize-area-of-square-hole-in-grid/solution.ts
function maximizeSquareHoleArea(n: number, m: number, hBars: number[], vBars: number[]): number {
  const maxH = longestStreak(hBars);
  const maxV = longestStreak(vBars);
  const side = Math.min(maxH, maxV);
  return side * side;
}

function longestStreak(bars: number[]): number {
  if (bars.length === class="syntax-number">0) {
    return class="syntax-number">1;
  }

  bars.sort((a, b) => a - b);

  let best = class="syntax-number">1;
  let current = class="syntax-number">1;

  for (let i = class="syntax-number">1; i < bars.length; ++i) {
    if (bars[i] === bars[i - class="syntax-number">1] + class="syntax-number">1) {
      current += class="syntax-number">1;
    } else if (bars[i] === bars[i - class="syntax-number">1]) {
      continue;
    } else {
      current = class="syntax-number">1;
    }
    if (current > best) {
      best = current;
    }
  }

  return best + class="syntax-number">1;
}

export { maximizeSquareHoleArea };