14 Oct 2025•TypeScript•Medium

Largest Plus Sign

find the largest plus sign order by computing longest consecutive 1s in four directions using dp.

for each cell, compute the longest streak of 1s in four directions: left, right, up, down. use separate passes for each direction to build these counts efficiently.

the order of a plus sign centered at a cell is the minimum of all four directional streaks. find the maximum order across all cells.

approach

build four 2d arrays for left, right, up, down streaks
for each direction, do a single pass to compute streaks
for each cell, take min of four directions as plus order
track the maximum order found

complexity

O(n²) time for four passes over the grid, O(n²) space for the four direction arrays. efficient dp solution.

Solution files

TypeScript•largest-plus-sign/solution.ts

function orderOfLargestPlusSign(n: number, mines: number[][]): number {
  const blocked = new Set<string>();
  for (const [r, c] of mines) {
    blocked.add(`${r},${c}`);
  }

  const left = Array.from({ length: n }, () => new Array<number>(n).fill(class="syntax-number">0));
  const right = Array.from({ length: n }, () => new Array<number>(n).fill(class="syntax-number">0));
  const up = Array.from({ length: n }, () => new Array<number>(n).fill(class="syntax-number">0));
  const down = Array.from({ length: n }, () => new Array<number>(n).fill(class="syntax-number">0));

  for (let r = class="syntax-number">0; r < n; ++r) {
    let streak = class="syntax-number">0;
    for (let c = class="syntax-number">0; c < n; ++c) {
      if (blocked.has(`${r},${c}`)) {
        streak = class="syntax-number">0;
      } else {
        streak += class="syntax-number">1;
      }
      left[r][c] = streak;
    }
  }

  for (let r = class="syntax-number">0; r < n; ++r) {
    let streak = class="syntax-number">0;
    for (let c = n - class="syntax-number">1; c >= class="syntax-number">0; --c) {
      if (blocked.has(`${r},${c}`)) {
        streak = class="syntax-number">0;
      } else {
        streak += class="syntax-number">1;
      }
      right[r][c] = streak;
    }
  }

  for (let c = class="syntax-number">0; c < n; ++c) {
    let streak = class="syntax-number">0;
    for (let r = class="syntax-number">0; r < n; ++r) {
      if (blocked.has(`${r},${c}`)) {
        streak = class="syntax-number">0;
      } else {
        streak += class="syntax-number">1;
      }
      up[r][c] = streak;
    }
  }

  for (let c = class="syntax-number">0; c < n; ++c) {
    let streak = class="syntax-number">0;
    for (let r = n - class="syntax-number">1; r >= class="syntax-number">0; --r) {
      if (blocked.has(`${r},${c}`)) {
        streak = class="syntax-number">0;
      } else {
        streak += class="syntax-number">1;
      }
      down[r][c] = streak;
    }
  }

  let best = class="syntax-number">0;
  for (let r = class="syntax-number">0; r < n; ++r) {
    for (let c = class="syntax-number">0; c < n; ++c) {
      if (blocked.has(`${r},${c}`)) {
        continue;
      }
      const order = Math.min(left[r][c], right[r][c], up[r][c], down[r][c]);
      if (order > best) {
        best = order;
      }
    }
  }

  return best;
}

export { orderOfLargestPlusSign };