DP Prefix sum Row and Col - Java O(N^3)|O(N^2)
Intuition\n Describe your first thoughts on how to solve this problem. \nCalcuate 2 DP tables, one (dpRow) for consecutive cell 1 in row and another (dpCol) for
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nCalcuate 2 DP tables, one (dpRow) for consecutive cell `1` in row and another (dpCol) for consecurity cell `1` in column. The min of each cell across the two DP tables is the longest possible length of right vertical side and bottom horizontal side of the square. \n\nThen for each cell, check the possible top horizontal side and left vertical side to see if they exist, capture the max along the way.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: $$O(N^3)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(N^2)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```java []\nclass Solution {\n    public int largest1BorderedSquare(int[][] grid) {\n        int n = grid.length + 1, m = grid[0].length + 1, res = 0;\n        int[][] dpRow = new int[n][m], dpCol = new int[n][m];\n        for (int i = 1; i < n; i++)\n            for (int j = 1; j < m; j++)\n                if (grid[i - 1][j - 1] != 0) {\n                    // prefix sum row and col\n                    dpRow[i][j] = dpRow[i][j - 1] + 1;\n                    dpCol[i][j] = dpCol[i - 1][j] + 1;\n                    // check square\n                    int side = Math.min(dpRow[i][j], dpCol[i][j]);\n                    for (int k = side; k > res; k--)\n                        if (i >= k && j >= k\n                                && dpRow[i - k + 1][j] >= k && dpCol[i][j - k + 1] >= k) {\n                            res = k;\n                            // System.out.printf("i:%d,j:%d,k:%d\\n", i, j, k);\n                            break;\n                        }\n                }\n        return res * res;\n    }\n}\n```
['Java']