✅Largest Plus Sign || DP W/ O(N^2) Approach || C++ | JAVA
IDEA\n\n Create the matrix of 1 and 0.\n Then, fill the DP matrix the following way:\n\t Iterate through the matrix in four ways - left to right, right to left,
**IDEA**\n\n* Create the matrix of `1` and `0`.\n* Then, fill the DP matrix the following way:\n\t* Iterate through the matrix in four ways - `left to right`, `right to left`, `top to bottom`, `bottom to top`.\n\t* Store in the `vectors for directions` the **maximum length of contiguous** `1`.\n* Hence we have a matrix where each position has the largest plus sign centered in that cell.\n* The maximum length from either directions will be our answer \n\n**SOLUTION**\n`IN C++`\n```\nint orderOfLargestPlusSign(int n, vector<vector<int>>& mines) {\n    vector<vector<int>> mat(n, vector<int>(n, 1)) ;\n    for(auto it : mines)\n    {\n        int x = it[0] ;\n        int y = it[1] ;\n        mat[x][y] = 0 ;\n    }\n    vector<vector<int>> lef, rig, top, bot ;\n    lef = rig = top = bot = mat ;\n    for(int i=0; i < n ; i++)\n    {\n        for(int j = 0 ; j < n ; j++)\n        {\n            int x = n - i - 1 ;\n            int y = n - j - 1 ;\n            if(i > 0   && top[i][j]) \n\t\t\t\ttop[i][j] += top[i-1][j];\n            if(j > 0 && lef[i][j]) \n\t\t\t\tlef[i][j] += lef[i][j-1];\n            if(x < n-1 && bot[x][y]) \n\t\t\t\tbot[x][y] += bot[x+1][y];\n            if(y < n-1 && rig[x][y]) \n\t\t\t\trig[x][y] += rig[x][y+1];\n        }\n    }\n    int ans = 0;\n    for(int i = 0 ; i < n ; i++)\n        for(int j = 0 ; j < n ; j++)\n            ans = max(ans, min({lef[i][j], rig[i][j], top[i][j], bot[i][j]}));\n\t\t\t\n    return ans;\n}\n```\n`In JAVA`\n```\nclass Solution {\n    public int orderOfLargestPlusSign(int n, int[][] mines) {        \n        boolean[][] mat = new boolean[n][n] ;\n        for(int[] pos:mines){\n            mat[pos[0]][pos[1]] = true;\n        }\n        int[][] left = new int[n][n];\n        int[][] right = new int[n][n];\n        int[][] up = new int[n][n];\n        int[][] down = new int[n][n];\n        int ans = 0;\n        // For Left and Up only\n        for(int i = 0 ; i < n ; i++){ \n            for(int j = 0 ; j < n ; j++){\n                left[i][j] = mat[i][j]?0:1+(j==0?0:left[i][j-1]);\n                up[i][j] = mat[i][j]?0:1+(i==0?0:up[i-1][j]);\n            }\n        }\n        // For Right and Down and simoultaneously get answer\n        for(int i = n - 1 ; i >= 0 ; i--){\n            for(int j = n - 1 ; j >= 0 ; j--){\n                right[i][j] = mat[i][j]?0:1+(j==n-1?0:right[i][j+1]);\n                down[i][j] = mat[i][j]?0:1+(i==n-1?0:down[i+1][j]);\n                int x = Math.min(Math.min(left[i][j],up[i][j]),Math.min(right[i][j],down[i][j]));\n                ans = Math.max(ans, x);\n            }\n        }\n        return ans ;\n    }\n};\n```\n**TIME COMPLEXITY - O(N^2)**\n**SPACE COMPLEXITY - O(N^2)**
[]