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.

&nbsp;
Example 1:

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:

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


&nbsp;
Constraints:


	1 &lt;= n &lt;= 500
	1 &lt;= mines.length &lt;= 5000
	0 &lt;= xi, yi &lt; n
	All the pairs (xi, yi) are unique.


class Solution:

    def orderOfLargestPlusSign(self, n: int, mines: list[list[int]]) -> int:
        matrix = [1] * n
        aux = {}
        hasOne = False
        for i in range(0,n):
            matrix[i] = [1] * n
        for mine in mines:
            matrix[mine[0]][mine[1]] = 0
        for i in range(0,n):
            for j in range(0,n):
                if(matrix[i][j] == 1):
                    hasOne = True
                if((i,j) not in aux):
                    aux[(i,j)] = {"t":0,"l":0,"r":0,"b":0}
                if(j>0 and matrix[i][j] == 1 and matrix[i][j-1] == 1):
                    aux[(i,j)]["l"] = aux[(i,j-1)]["l"] + 1  
                if(i>0 and matrix[i][j] == 1 and matrix[i-1][j] == 1):
                    aux[(i,j)]["t"] = aux[(i-1,j)]["t"] + 1
        
        maxOrder = 0 
        for i in range(n-1,-1,-1):
            if(i<maxOrder):
                    break
            for j in range(n-1,-1,-1):
                if(j<maxOrder):
                    break
                if(j<n-1 and matrix[i][j] == 1 and matrix[i][j+1] == 1):
                    aux[(i,j)]["r"] = aux[(i,j+1)]["r"] + 1  
                if(i<n-1 and matrix[i][j] == 1 and matrix[i+1][j]):
                    aux[(i,j)]["b"] = aux[(i+1,j)]["b"] + 1
                maxOrder = max(min(aux[(i,j)]["b"],aux[(i,j)]["t"],aux[(i,j)]["r"],aux[(i,j)]["l"]),maxOrder)
 
        print(maxOrder+1)
        return maxOrder + 1 
class Solution {
    public int orderOfLargestPlusSign(int n, int[][] mines) {
        // Create the matrix
        int[][] arr = new int[n][n];
        for(int[] subArray : arr) {
            Arrays.fill(subArray, 1);
        }

        for(int i = 0; i < mines.length; i++) {
            arr[mines[i][0]][mines[i][1]] = 0;
        }

        // Prefix Count DP arrays
        int[][] dpTop = new int[arr.length][arr.length];
        int[][] dpLeft = new int[arr.length][arr.length];
        int[][] dpRight = new int[arr.length][arr.length];
        int[][] dpBottom = new int[arr.length][arr.length];

        // Prefix count of 1 cells on top and left directions
        for(int i = 0; i < arr.length; i++) {
            for(int j = 0; j < arr.length; j++) {
                if(i - 1 >= 0 && arr[i - 1][j] == 1) {
                    dpTop[i][j] = 1 + dpTop[i - 1][j];
                }

                if(j - 1 >= 0 && arr[i][j - 1] == 1) {
                    dpLeft[i][j] = 1 + dpLeft[i][j - 1];
                }
            }
        }

        // Prefix count of 1 cells on bottom and right directions
        for(int i = arr.length - 1; i >= 0; i--) {
            for(int j = arr.length - 1; j >= 0; j--) {
                if(i + 1 < arr.length && arr[i + 1][j] == 1) {
                    dpBottom[i][j] = 1 + dpBottom[i + 1][j];
                }

                if(j + 1 < arr.length && arr[i][j + 1] == 1) {
                    dpRight[i][j] = 1 + dpRight[i][j + 1];
                }
            }
        }

        int maxPlusSignLength = 0;
        for(int i = 0; i < arr.length; i++) {
            for(int j = 0; j < arr.length; j++) {
                if(arr[i][j] == 0) continue;

                // Minimum adjacent 1 cell count from all four directions to ensure symmetry
                int minAdjacentOnes = Math.min(Math.min(dpTop[i][j], dpBottom[i][j]), Math.min(dpLeft[i][j], dpRight[i][j]));
                maxPlusSignLength = Math.max(maxPlusSignLength, minAdjacentOnes + 1);
            }
        }

        return maxPlusSignLength;
    }
}
class Solution {
public:
    int orderOfLargestPlusSign(int n, vector<vector<int>>& mines) {
        //jai shri ram
        int ans=0;
        vector<bool>block(25*int(1e4)+1,0);
        vector<vector<int>>dp(n,vector<int>(n,0));
        for(auto x:mines){
            int a=x[0],b=x[1];
            block[a*n+b]=true;
        }
        for(int i=0;i<n;i++){
            int sum=0;
            for(int j=0;j<n;j++){
                if(block[i*n+j]){
                    sum=0;
                }else {
                    sum+=1;
                }
                dp[i][j]=sum;
            }
        }
        for(int j=0;j<n;j++){
            int sum=0;
            for(int i=0;i<n;i++){
                if(block[i*n+j]){
                    sum=0;
                }else sum+=1;
                dp[i][j]=min(dp[i][j],sum);
            }
        }
        for(int j=n-1;j>=0;j--){
            int sum=0;
            for(int i=n-1;i>=0;i--){
                if(block[i*n+j]){
                    sum=0;
                }else sum+=1;
                dp[i][j]=min(dp[i][j],sum);
            }
        }
        for(int i=n-1;i>=0;i--){
            int sum=0;
            for(int j=n-1;j>=0;j--){
                if(block[i*n+j]){
                    sum=0;
                }else sum+=1;
                dp[i][j]=min(dp[i][j],sum);
                ans=max(ans,dp[i][j]);
            }
        }
        return ans;
    }
};
/**
 * @param {number} n
 * @param {number[][]} mines
 * @return {number}
 */
var orderOfLargestPlusSign = function(n, mines) {
    // create n * n as a table, and each grid fill the maximum number
    const t = new Array(n).fill(0).map(() => new Array(n).fill(n));

    // insert `0` to the grid in table according the position in mines
    mines.forEach(a => t[a[0]][a[1]] = 0);

    // loop each rows and cols
    // - for rows: calculate non-zero grid from left to right
    // - for cols: calculate non-zero grid from top to bottom
    // - when the loop is completed, all of non-zero values will be calculated by four directions
    // - and these grids value will be updated by comparing. then we can obtain the minimum value of the four directions caculation, which is the maximum of the grid
    for (let i = 0; i < n; i++) {
        // save the maximum value of non-zeros with for directions
        let [l, r, u, d] = [0, 0, 0, 0];

        // l: left,  loop row i from left to right
        // r: right, loop row i from right to left
        // u: up,    loop col i from top to bottom
        // d: down,  loop col i from bottom to top
        for (let j = 0, k = n - 1; j < n; j++, k--) {
            // if the value is `0`, then set variable to `0`, and indicates it's broken
            l = t[i][j] && l + 1;
            r = t[i][k] && r + 1;
            u = t[j][i] && u + 1;
            d = t[k][i] && d + 1;

            // if current value is less than origin value
            // one possibility: the origin value is default
            // another possibility: the length of non-zero in a centain direction is langer than in the current direction, which the minimum value we need
            if (l < t[i][j]) t[i][j] = l;
            if (r < t[i][k]) t[i][k] = r;
            if (u < t[j][i]) t[j][i] = u;
            if (d < t[k][i]) t[k][i] = d;
        }
    }

    // return maximum value be saved by all cells
    return Math.max(...t.map(v => Math.max(...v)));
}
Largest Plus Sign