Largest Plus Sign

medium dp grid prefix

Problem

Given an n x n grid where mines mark zero cells, return the order of the largest axis-aligned plus sign of ones that can fit (arm length k means total side 2k-1).

Inputn=5, mines=[[4,2]]

Output2

A plus sign of order 2 fits but not order 3 because of the mine.

input

def orderOfLargestPlusSign(n, mines):
    bad = {tuple(m) for m in mines}
    dp = [[n]*n for _ in range(n)]
    for i in range(n):
        l = r = u = d = 0
        for j in range(n):
            l = 0 if (i,j) in bad else l+1
            dp[i][j] = min(dp[i][j], l)
            r = 0 if (i,n-1-j) in bad else r+1
            dp[i][n-1-j] = min(dp[i][n-1-j], r)
            u = 0 if (j,i) in bad else u+1
            dp[j][i] = min(dp[j][i], u)
            d = 0 if (n-1-j,i) in bad else d+1
            dp[n-1-j][i] = min(dp[n-1-j][i], d)
    return max(max(row) for row in dp)

function orderOfLargestPlusSign(n, mines) {
  const bad = new Set(mines.map(([a,b]) => a*n+b));
  const dp = Array.from({length:n}, () => new Array(n).fill(n));
  for (let i = 0; i < n; i++) {
    let l=0,r=0,u=0,d=0;
    for (let j = 0; j < n; j++) {
      l = bad.has(i*n+j) ? 0 : l+1; dp[i][j] = Math.min(dp[i][j], l);
      r = bad.has(i*n+(n-1-j)) ? 0 : r+1; dp[i][n-1-j] = Math.min(dp[i][n-1-j], r);
      u = bad.has(j*n+i) ? 0 : u+1; dp[j][i] = Math.min(dp[j][i], u);
      d = bad.has((n-1-j)*n+i) ? 0 : d+1; dp[n-1-j][i] = Math.min(dp[n-1-j][i], d);
    }
  }
  let ans = 0;
  for (const row of dp) for (const v of row) ans = Math.max(ans, v);
  return ans;
}

int orderOfLargestPlusSign(int n, int[][] mines) {
    Set<Integer> bad = new HashSet<>();
    for (int[] m : mines) bad.add(m[0]*n + m[1]);
    int[][] dp = new int[n][n];
    for (int[] r : dp) Arrays.fill(r, n);
    for (int i = 0; i < n; i++) {
        int l=0,r=0,u=0,d=0;
        for (int j = 0; j < n; j++) {
            l = bad.contains(i*n+j) ? 0 : l+1; dp[i][j] = Math.min(dp[i][j], l);
            r = bad.contains(i*n+(n-1-j)) ? 0 : r+1; dp[i][n-1-j] = Math.min(dp[i][n-1-j], r);
            u = bad.contains(j*n+i) ? 0 : u+1; dp[j][i] = Math.min(dp[j][i], u);
            d = bad.contains((n-1-j)*n+i) ? 0 : d+1; dp[n-1-j][i] = Math.min(dp[n-1-j][i], d);
        }
    }
    int ans = 0;
    for (int[] row : dp) for (int v : row) ans = Math.max(ans, v);
    return ans;
}

int orderOfLargestPlusSign(int n, vector<vector<int>>& mines) {
    unordered_set<int> bad;
    for (auto& m : mines) bad.insert(m[0]*n + m[1]);
    vector<vector<int>> dp(n, vector<int>(n, n));
    for (int i = 0; i < n; i++) {
        int l=0,r=0,u=0,d=0;
        for (int j = 0; j < n; j++) {
            l = bad.count(i*n+j) ? 0 : l+1; dp[i][j] = min(dp[i][j], l);
            r = bad.count(i*n+(n-1-j)) ? 0 : r+1; dp[i][n-1-j] = min(dp[i][n-1-j], r);
            u = bad.count(j*n+i) ? 0 : u+1; dp[j][i] = min(dp[j][i], u);
            d = bad.count((n-1-j)*n+i) ? 0 : d+1; dp[n-1-j][i] = min(dp[n-1-j][i], d);
        }
    }
    int ans = 0;
    for (auto& row : dp) for (int v : row) ans = max(ans, v);
    return ans;
}

Explanation

A "plus sign" of order k is a center cell with four arms of k ones reaching up, down, left and right. We want the biggest order that fits in a grid where mines are zeros. The key idea is that a center's order equals the shortest of its four arms.

So for every cell we compute, in each of the four directions, how many consecutive 1s run outward. The plus that can sit there is limited by the smallest of those four lengths, which is exactly min(left, right, up, down).

The code is clever about it: dp[i][j] starts at n, and a single sweep counts run lengths in all four directions at once (resetting the counter to 0 whenever it hits a mine), each time keeping the minimum seen so far in dp.

At the end the answer is the largest value in dp — the best center's smallest arm.

Example: n=5 with a mine at [4,2]. The mine blocks an order-3 plus near the bottom, but an order-2 plus still fits, so the answer is 2.

Time: O(n^2) Space: O(n^2)