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

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.

Example 2

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.

Solution

Method 1 – Dynamic Programming Four Directions

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 is updated in four passes.
  • 🧺 Space complexity: O(n^2) — For the grid.