Problem

You are given an integer n. You have an n x n binary grid grid with all values initially 1’s except for some indices given in the array mines. The ith element of the array mines is defined as mines[i] = [xi, yi] where grid[xi][yi] == 0.

Return the order of the largest axis-aligned plus sign of 1_’s contained in_ grid. If there is none, return 0.

An axis-aligned plus sign of 1’s of order k has some center grid[r][c] == 1 along with four arms of length k - 1 going up, down, left, and right, and made of 1’s. Note that there could be 0’s or 1’s beyond the arms of the plus sign, only the relevant area of the plus sign is checked for 1’s.

Examples

Example 1

$$ \Huge \begin{array}{|c|c|c|c|c|}\hline 1 & 1 & 1 & 1 & 1 \\ \hline 1 & 1 & 1 & 1 & 1 \\ \hline 1 & \color{purple}{1} & 1 & 1 & 1 \\ \hline \color{purple}1 & \color{purple}1 & \color{purple}{1} & 1 & 1 \\ \hline 1 & \color{purple}1 & 0 & 1 & 1 \\ \hline \end{array} $$

1
2
3

Input: n = 5, mines = [[4,2]]
Output: 2
Explanation: In the above grid, the largest plus sign can only be of order 2. One of them is shown.

Visual (center at (2,2); order = 2 ⇒ arm length = 1):

Example 2

$$ \Huge \begin{array}{|c|} \hline 0 \\ \hline \end{array} $$

1
2
3

Input: n = 1, mines = [[0,0]]
Output: 0
Explanation: There is no plus sign, so return 0.

Constraints

  • 1 <= n <= 500
  • 1 <= mines.length <= 5000
  • 0 <= xi, yi < n
  • All the pairs (xi, yi) are unique.

Follow up

What if the matrix is not N×N but M×N? What if the matrix is very sparse (only P ones, with P << M*N)? OR What if we also need to return the coordinates of the center of the plus/cross sign. Here is the answer to it: : Largest cross in a sparse matrix.

Solution

Method 1 - Dynamic Programming Four Directions (Order Only)

Intuition

For each cell, the order of the plus sign is determined by the minimum number of consecutive 1’s in all four directions (up, down, left, right). We precompute these values using dynamic programming.

Approach

  1. Initialize a grid with all 1’s and set mines to 0.
  2. For each cell, compute the number of consecutive 1’s in all four directions:
    • Left to right
    • Right to left
    • Top to bottom
    • Bottom to top
  3. For each cell, the order is the minimum of the four values.
  4. The answer is the maximum order among all cells.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
public:
    int orderOfLargestPlusSign(int n, vector<vector<int>>& mines) {
        vector<vector<int>> grid(n, vector<int>(n, n));
        for (auto& m : mines) grid[m[0]][m[1]] = 0;
        for (int i = 0; i < n; ++i) {
            int l = 0, r = 0;
            for (int j = 0, k = n-1; j < n; ++j, --k) {
                l = grid[i][j] ? l+1 : 0;
                grid[i][j] = min(grid[i][j], l);
                r = grid[i][k] ? r+1 : 0;
                grid[i][k] = min(grid[i][k], r);
            }
        }
        for (int j = 0; j < n; ++j) {
            int u = 0, d = 0;
            for (int i = 0, k = n-1; i < n; ++i, --k) {
                u = grid[i][j] ? u+1 : 0;
                grid[i][j] = min(grid[i][j], u);
                d = grid[k][j] ? d+1 : 0;
                grid[k][j] = min(grid[k][j], d);
            }
        }
        int ans = 0;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                ans = max(ans, grid[i][j]);
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

func orderOfLargestPlusSign(n int, mines [][]int) int {
    grid := make([][]int, n)
    for i := range grid {
        grid[i] = make([]int, n)
        for j := range grid[i] {
            grid[i][j] = n
        }
    }
    for _, m := range mines {
        grid[m[0]][m[1]] = 0
    }
    for i := 0; i < n; i++ {
        l, r := 0, 0
        for j, k := 0, n-1; j < n; j, k = j+1, k-1 {
            if grid[i][j] != 0 {
                l++
            } else {
                l = 0
            }
            grid[i][j] = min(grid[i][j], l)
            if grid[i][k] != 0 {
                r++
            } else {
                r = 0
            }
            grid[i][k] = min(grid[i][k], r)
        }
    }
    for j := 0; j < n; j++ {
        u, d := 0, 0
        for i, k := 0, n-1; i < n; i, k = i+1, k-1 {
            if grid[i][j] != 0 {
                u++
            } else {
                u = 0
            }
            grid[i][j] = min(grid[i][j], u)
            if grid[k][j] != 0 {
                d++
            } else {
                d = 0
            }
            grid[k][j] = min(grid[k][j], d)
        }
    }
    ans := 0
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            if grid[i][j] > ans {
                ans = grid[i][j]
            }
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
    public int orderOfLargestPlusSign(int n, int[][] mines) {
        int[][] grid = new int[n][n];
        for (int i = 0; i < n; ++i) Arrays.fill(grid[i], n);
        for (int[] m : mines) grid[m[0]][m[1]] = 0;
        for (int i = 0; i < n; ++i) {
            int l = 0, r = 0;
            for (int j = 0, k = n-1; j < n; ++j, --k) {
                l = grid[i][j] != 0 ? l+1 : 0;
                grid[i][j] = Math.min(grid[i][j], l);
                r = grid[i][k] != 0 ? r+1 : 0;
                grid[i][k] = Math.min(grid[i][k], r);
            }
        }
        for (int j = 0; j < n; ++j) {
            int u = 0, d = 0;
            for (int i = 0, k = n-1; i < n; ++i, --k) {
                u = grid[i][j] != 0 ? u+1 : 0;
                grid[i][j] = Math.min(grid[i][j], u);
                d = grid[k][j] != 0 ? d+1 : 0;
                grid[k][j] = Math.min(grid[k][j], d);
            }
        }
        int ans = 0;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                ans = Math.max(ans, grid[i][j]);
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution {
    fun orderOfLargestPlusSign(n: Int, mines: Array<IntArray>): Int {
        val grid = Array(n) { IntArray(n) { n } }
        for (m in mines) grid[m[0]][m[1]] = 0
        for (i in 0 until n) {
            var l = 0; var r = 0
            for (j in 0 until n) {
                l = if (grid[i][j] != 0) l+1 else 0
                grid[i][j] = minOf(grid[i][j], l)
                val k = n-1-j
                r = if (grid[i][k] != 0) r+1 else 0
                grid[i][k] = minOf(grid[i][k], r)
            }
        }
        for (j in 0 until n) {
            var u = 0; var d = 0
            for (i in 0 until n) {
                u = if (grid[i][j] != 0) u+1 else 0
                grid[i][j] = minOf(grid[i][j], u)
                val k = n-1-i
                d = if (grid[k][j] != 0) d+1 else 0
                grid[k][j] = minOf(grid[k][j], d)
            }
        }
        var ans = 0
        for (i in 0 until n)
            for (j in 0 until n)
                ans = maxOf(ans, grid[i][j])
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution:
    def orderOfLargestPlusSign(self, n: int, mines: list[list[int]]) -> int:
        grid = [[n]*n for _ in range(n)]
        for x, y in mines:
            grid[x][y] = 0
        for i in range(n):
            l = r = 0
            for j in range(n):
                l = l+1 if grid[i][j] else 0
                grid[i][j] = min(grid[i][j], l)
                k = n-1-j
                r = r+1 if grid[i][k] else 0
                grid[i][k] = min(grid[i][k], r)
        for j in range(n):
            u = d = 0
            for i in range(n):
                u = u+1 if grid[i][j] else 0
                grid[i][j] = min(grid[i][j], u)
                k = n-1-i
                d = d+1 if grid[k][j] else 0
                grid[k][j] = min(grid[k][j], d)
        ans = 0
        for i in range(n):
            for j in range(n):
                ans = max(ans, grid[i][j])
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

impl Solution {
    pub fn order_of_largest_plus_sign(n: i32, mines: Vec<Vec<i32>>) -> i32 {
        let n = n as usize;
        let mut grid = vec![vec![n as i32; n]; n];
        for m in mines {
            grid[m[0] as usize][m[1] as usize] = 0;
        }
        for i in 0..n {
            let (mut l, mut r) = (0, 0);
            for j in 0..n {
                l = if grid[i][j] != 0 { l+1 } else { 0 };
                grid[i][j] = grid[i][j].min(l);
                let k = n-1-j;
                r = if grid[i][k] != 0 { r+1 } else { 0 };
                grid[i][k] = grid[i][k].min(r);
            }
        }
        for j in 0..n {
            let (mut u, mut d) = (0, 0);
            for i in 0..n {
                u = if grid[i][j] != 0 { u+1 } else { 0 };
                grid[i][j] = grid[i][j].min(u);
                let k = n-1-i;
                d = if grid[k][j] != 0 { d+1 } else { 0 };
                grid[k][j] = grid[k][j].min(d);
            }
        }
        let mut ans = 0;
        for i in 0..n {
            for j in 0..n {
                ans = ans.max(grid[i][j]);
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
    orderOfLargestPlusSign(n: number, mines: number[][]): number {
        const grid = Array.from({length: n}, () => Array(n).fill(n));
        for (const [x, y] of mines) grid[x][y] = 0;
        for (let i = 0; i < n; ++i) {
            let l = 0, r = 0;
            for (let j = 0, k = n-1; j < n; ++j, --k) {
                l = grid[i][j] ? l+1 : 0;
                grid[i][j] = Math.min(grid[i][j], l);
                r = grid[i][k] ? r+1 : 0;
                grid[i][k] = Math.min(grid[i][k], r);
            }
        }
        for (let j = 0; j < n; ++j) {
            let u = 0, d = 0;
            for (let i = 0, k = n-1; i < n; ++i, --k) {
                u = grid[i][j] ? u+1 : 0;
                grid[i][j] = Math.min(grid[i][j], u);
                d = grid[k][j] ? d+1 : 0;
                grid[k][j] = Math.min(grid[k][j], d);
            }
        }
        let ans = 0;
        for (let i = 0; i < n; ++i)
            for (let j = 0; j < n; ++j)
                ans = Math.max(ans, grid[i][j]);
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n^2) – Each cell participates in four directional passes (two row + two column sweeps).
  • 🧺 Space complexity: O(n^2) – Stores the compressed directional minima in-place (can be reduced to O(n) auxiliary if four separate arrays are streamed).

Extended Methods (2 & 3) with full code have been moved under the Follow up section to keep the primary LeetCode solution concise.

Complexity

  • ⏰ Time complexity: O(n^2) – Each cell participates in four directional passes (two row + two column sweeps).
  • 🧺 Space complexity: O(n^2) – Stores the compressed directional minima in-place (can be reduced to O(n) auxiliary if four separate arrays are streamed).