Largest Plus Sign

Problem Statement

In an n x n grid initially filled with 1s, some cells are marked as mines and set to 0. Find the order (arm length + 1) of the largest axis-aligned plus sign of 1s centered at a non-mined cell.

A plus sign of order k has a center plus four arms of k-1 ones each in the up, down, left, and right directions. Order 1 means just the center cell (still needs to be non-mined).

Example 1:

Input: n = 5, mines = [[4, 2]]
Output: 2
Explanation: The largest plus sign of 1s has arms of length 1 (order 2) centered at many cells.

Example 2:

Input: n = 1, mines = [[0, 0]]
Output: 0
Explanation: The only cell is mined, so no plus sign exists.

Constraints:

1 <= n <= 500
0 <= mines.length <= 5000

Difficulty: Medium

Pattern Recognition

What is the structure of the input? A 2D grid implicitly defined by n and a sparse list of zero cells.
What are we optimizing? The largest plus-sign order that fits.
What pattern does this suggest? DP on grid — compute, for every cell, the longest run of 1s extending in each of four directions. The plus-order at (r, c) is the minimum of the four.
Why does this pattern fit? The four directional runs are independent 1D subproblems. Each run can be built incrementally in a single sweep per direction.

Approach

Brute Force — Expand Outward

For each non-mined cell, expand arms outward until you hit a mine or the boundary. Track the max.

Time: O(n^3) — for each of n^2 centers, arms expand up to n. Space: O(m) for the mine set. Why insufficient: n up to 500 gives ~1.25 * 10^8 ops. Borderline TLE, and easy to blow past with constant factors.

Optimal — Four Directional Sweeps

Key Insight: Each directional run is the result of a single pass that resets to 0 at mines and increments otherwise. Store the minimum of the four runs per cell; that's the plus order at that cell.

Step-by-step:

Build mineSet for O(1) lookup.
Initialize grid[r][c] = n (an upper bound).
For each row, sweep left-to-right maintaining a running count of consecutive non-mined cells (reset to 0 at mines). Write min(grid[r][c], count). Then sweep right-to-left similarly.
Repeat column-wise for up and down.
Each cell's final value is the min of the four runs — the plus order centered there.
Return the maximum.

Time: O(n^2). Space: O(n^2) for the grid plus O(m) for the mine set.

Walkthrough

n = 3, mines = [[1, 1]]. Grid:

1 1 1
1 0 1
1 1 1

Initialize grid[r][c] = 3.

Row sweep left-to-right (counts non-mined run from the left):

Row 0: 1, 2, 3 -> grid[0] min'd: 1, 2, 3 Row 1: 1, 0, 1 -> grid[1] min'd: 1, 0, 1 Row 2: 1, 2, 3 -> grid[2] min'd: 1, 2, 3

Row sweep right-to-left:

Row 0: 3, 2, 1 -> min: 1, 2, 1 Row 1: 1, 0, 1 -> min: 1, 0, 1 Row 2: 3, 2, 1 -> min: 1, 2, 1

Column sweep top-to-bottom:

Col 0: 1, 2, 3 -> min with existing: 1, 2, 1 Col 1: 1, 0, 1 -> min: 1, 0, 1 Col 2: 1, 2, 3 -> min: 1, 2, 1

Column sweep bottom-to-top:

Col 0: 3, 2, 1 -> min: 1, 2, 1 Col 1: 1, 0, 1 -> min: 1, 0, 1 Col 2: 3, 2, 1 -> min: 1, 2, 1

Final grid:

1 2 1
1 0 1 (wait — grid[1][1]=0 because (1,1) is a mine, so center can't be there)
1 2 1

Actually corrected — after all four sweeps, grid[1][1]=0 (mine), and the max among other cells is 1. But wait, grid[1][0] is actually 1 (bounded by leftmost column). Hmm, the interior cells don't qualify because the mine kills any plus centered there. Answer: 1 (order 1 plus signs exist, but nothing larger).

Rework with n = 5, mines = [[4, 2]] would give answer 2.

Implementation

TypeScriptC++

typescript

function orderOfLargestPlusSign(n: number, mines: number[][]): number {
  const grid: number[][] = Array.from({ length: n }, () => new Array(n).fill(n));
  const mineSet = new Set(mines.map(([r, c]) => r * n + c));

  for (let r = 0; r < n; r++) {
    let left = 0, right = 0;
    for (let c = 0; c < n; c++) {
      left = mineSet.has(r * n + c) ? 0 : left + 1;
      grid[r][c] = Math.min(grid[r][c], left);
    }
    for (let c = n - 1; c >= 0; c--) {
      right = mineSet.has(r * n + c) ? 0 : right + 1;
      grid[r][c] = Math.min(grid[r][c], right);
    }
  }
  for (let c = 0; c < n; c++) {
    let up = 0, down = 0;
    for (let r = 0; r < n; r++) {
      up = mineSet.has(r * n + c) ? 0 : up + 1;
      grid[r][c] = Math.min(grid[r][c], up);
    }
    for (let r = n - 1; r >= 0; r--) {
      down = mineSet.has(r * n + c) ? 0 : down + 1;
      grid[r][c] = Math.min(grid[r][c], down);
    }
  }

  let best = 0;
  for (let r = 0; r < n; r++)
    for (let c = 0; c < n; c++)
      best = Math.max(best, grid[r][c]);
  return best;
}

cpp

class Solution {
public:
    int orderOfLargestPlusSign(int n, vector<vector<int>>& mines) {
        vector<vector<int>> grid(n, vector<int>(n, n));
        unordered_set<int> mineSet;
        for (auto& m : mines) mineSet.insert(m[0] * n + m[1]);

        for (int r = 0; r < n; ++r) {
            int left = 0, right = 0;
            for (int c = 0; c < n; ++c) {
                left = mineSet.count(r*n+c) ? 0 : left + 1;
                grid[r][c] = min(grid[r][c], left);
            }
            for (int c = n-1; c >= 0; --c) {
                right = mineSet.count(r*n+c) ? 0 : right + 1;
                grid[r][c] = min(grid[r][c], right);
            }
        }
        for (int c = 0; c < n; ++c) {
            int up = 0, down = 0;
            for (int r = 0; r < n; ++r) {
                up = mineSet.count(r*n+c) ? 0 : up + 1;
                grid[r][c] = min(grid[r][c], up);
            }
            for (int r = n-1; r >= 0; --r) {
                down = mineSet.count(r*n+c) ? 0 : down + 1;
                grid[r][c] = min(grid[r][c], down);
            }
        }

        int best = 0;
        for (int r = 0; r < n; ++r)
            for (int c = 0; c < n; ++c)
                best = max(best, grid[r][c]);
        return best;
    }
};

Watch out: Initialize grid to n, not 0. You want to take a min against incoming counts; starting at 0 makes every cell stay 0.

Watch out: The plus "order" counts the center, so order = min-run-length including the center. A cell with 0 means it is itself a mine.

Watch out: Encoding mines as r * n + c is a cheap flat-int hash. Using "r,c" strings works but is slower.

Complexity Analysis

	Time	Space
Brute Force Expansion	O(n^3)	O(m)
Four Sweeps DP	O(n^2)	O(n^2)

Bottleneck: You must look at every cell, and each cell gets touched O(1) per direction for O(4) = O(1) total. n^2 is the floor.

Edge Cases

No mines — Answer is (n + 1) / 2 (integer division) — the biggest plus fits in the center.
Every cell mined — Answer is 0.
Mine at border — It only kills plus signs centered at itself and its 4-neighbors.
Very sparse mines — Answer likely close to (n+1)/2; the sweeps still run in full O(n^2).
n = 1 — Answer is 0 if the single cell is mined, else 1.

LC 221 — Maximal Square: DP on grid for largest all-1 square — similar "min of directions" idea.
LC 1139 — Largest 1-Bordered Square: Same 4-direction DP to compute run lengths.
LC 85 — Maximal Rectangle: Histogram transform per row.
LC 1504 — Count Submatrices With All Ones: Prefix-ones per column + counting.

What Is Expected at Each Level?

Junior / New Grad: Reach brute-force expansion. With a hint about "min of directional runs," get to the four-sweep approach.

Mid-level: Derive the four-sweep DP independently, write it correctly, and analyze complexity. Handle the mine-set representation cleanly.

Senior: Discuss the sparse-mines variant (n=10^6, 1000 mines) — the dense grid no longer fits, so switch to sorted-per-row structures and binary search for nearest mine. Discuss reduction to LC 221 when the plus degenerates into a square.

Largest Plus Sign ​

Problem Statement ​

Pattern Recognition ​

Approach ​

Brute Force — Expand Outward ​

Optimal — Four Directional Sweeps ​

Walkthrough ​

Implementation ​

Complexity Analysis ​

Edge Cases ​

Related Problems ​

What Is Expected at Each Level? ​