LeetCode 764 – Order of Largest Plus Sign: Problem Explanation and Multi‑Language Solutions

The problem asks for the order of the largest plus sign consisting only of cells with value 1 in an n × n grid where certain cells are set to 0 (the mines). If no such plus sign exists, the answer is 0 .

For a plus sign of order k , the central cell and the four arms extending k‑1 cells in the up, down, left, and right directions must all be 1 . Only the cells belonging to the plus sign are required to be 1 ; other cells may be 0 or 1 .

Example 1 (n = 5, mines = [[4,2]]): the largest plus sign has order 2.

Example 2 (n = 1, mines = [[0,0]]): no plus sign exists, answer is 0.

Approach – Preprocess + Simulation

For each cell we compute the length of consecutive 1 s in the four directions (up, down, left, right). This can be done with four prefix‑style DP matrices a , b , c , and d . The order of a plus sign centered at a cell is the minimum of the four directional lengths.

Algorithm steps:

Initialize the grid with 1 s and set mines to 0 .

Fill a (left) and b (up) by scanning from top‑left to bottom‑right.

Fill c (right) and d (down) by scanning from bottom‑right to top‑left.

For each cell, compute order = min(a[i][j], b[i][j], c[i][j], d[i][j]) and keep the maximum.

The preprocessing runs in O(n²) time and uses O(n²) extra space, which easily fits the constraints.

Complexity

Time complexity: O(n²) . Space complexity: O(n²) (four auxiliary matrices plus the original grid).

Reference Implementations

Java:

class Solution {
    public int orderOfLargestPlusSign(int n, int[][] mines) {
        int[][] g = new int[n + 10][n + 10];
        for (int i = 1; i <= n; i++) Arrays.fill(g[i], 1);
        for (int[] info : mines) g[info[0] + 1][info[1] + 1] = 0;
        int[][] a = new int[n + 10][n + 10];
        int[][] b = new int[n + 10][n + 10];
        int[][] c = new int[n + 10][n + 10];
        int[][] d = new int[n + 10][n + 10];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (g[i][j] == 1) {
                    a[i][j] = a[i - 1][j] + 1;
                    b[i][j] = b[i][j - 1] + 1;
                }
                if (g[n + 1 - i][n + 1 - j] == 1) {
                    c[n + 1 - i][n + 1 - j] = c[n + 2 - i][n + 1 - j] + 1;
                    d[n + 1 - i][n + 1 - j] = d[n + 1 - i][n + 2 - j] + 1;
                }
            }
        }
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                ans = Math.max(ans, Math.min(Math.min(a[i][j], b[i][j]), Math.min(c[i][j], d[i][j])));
            }
        }
        return ans;
    }
}

C++:

class Solution {
public:
    int orderOfLargestPlusSign(int n, vector
>& mines) {
        vector
> g(n + 10, vector
(n + 10, 1));
        for (auto& info : mines) g[info[0] + 1][info[1] + 1] = 0;
        vector
> a(n + 10, vector
(n + 10, 0)),
                        b(n + 10, vector
(n + 10, 0)),
                        c(n + 10, vector
(n + 10, 0)),
                        d(n + 10, vector
(n + 10, 0));
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (g[i][j] == 1) {
                    a[i][j] = a[i-1][j] + 1;
                    b[i][j] = b[i][j-1] + 1;
                }
                if (g[n+1-i][n+1-j] == 1) {
                    c[n+1-i][n+1-j] = c[n+2-i][n+1-j] + 1;
                    d[n+1-i][n+1-j] = d[n+1-i][n+2-j] + 1;
                }
            }
        }
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                ans = max(ans, min(min(a[i][j], b[i][j]), min(c[i][j], d[i][j])));
            }
        }
        return ans;
    }
};

Python:

class Solution:
    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:
        g = [[1] * (n + 10) for _ in range(n + 10)]
        for x, y in mines:
            g[x + 1][y + 1] = 0
        a = b = c = d = [[0] * (n + 10) for _ in range(n + 10)]
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                if g[i][j] == 1:
                    a[i][j] = a[i-1][j] + 1
                    b[i][j] = b[i][j-1] + 1
                if g[n + 1 - i][n + 1 - j] == 1:
                    c[n + 1 - i][n + 1 - j] = c[n + 2 - i][n + 1 - j] + 1
                    d[n + 1 - i][n + 1 - j] = d[n + 1 - i][n + 2 - j] + 1
        ans = 0
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                ans = max(ans, min(a[i][j], b[i][j], c[i][j], d[i][j]))
        return ans

TypeScript:

function orderOfLargestPlusSign(n: number, mines: number[][]): number {
    const getMat = (x: number, y: number, val: number): number[][] => {
        const ans = new Array
(x);
        for (let i = 0; i < x; i++) ans[i] = new Array
(y).fill(val);
        return ans;
    };
    const g = getMat(n + 10, n + 10, 1);
    for (const info of mines) g[info[0] + 1][info[1] + 1] = 0;
    const a = getMat(n + 10, n + 10, 0);
    const b = getMat(n + 10, n + 10, 0);
    const c = getMat(n + 10, n + 10, 0);
    const d = getMat(n + 10, n + 10, 0);
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= n; j++) {
            if (g[i][j] == 1) {
                a[i][j] = a[i - 1][j] + 1;
                b[i][j] = b[i][j - 1] + 1;
            }
            if (g[n + 1 - i][n + 1 - j] == 1) {
                c[n + 1 - i][n + 1 - j] = c[n + 2 - i][n + 1 - j] + 1;
                d[n + 1 - i][n + 1 - j] = d[n + 1 - i][n + 2 - j] + 1;
            }
        }
    }
    let ans = 0;
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= n; j++) {
            ans = Math.max(ans, Math.min(a[i][j], b[i][j], c[i][j], d[i][j]));
        }
    }
    return ans;
}

The solution efficiently determines the maximum plus sign order by leveraging four directional DP arrays, achieving linear‑time processing relative to the grid size.