O(n^3) tiny solution
\nHow to avoid repetitive computations in 2d array? Usually, "prefix sum" and "dp". \n\nMaintain two 2d arrays for max "1-border" length ending in i and j respe
\nHow to avoid repetitive computations in 2d array? Usually, "prefix sum" and "dp". \n\nMaintain two 2d arrays for max "1-border" length ending in `i` and `j` respectively. At each `(i, j)`, try to form a "1-square-border". \n\nBased on the 2d arrays, we immediately form the lower border with length `row[i][j]` and right border with length `col[i][j]`. The square border length must be smaller than `len = min(row[i][j], col[i][j])`. To find the longest border length, for l = `len,..., 3, 2, 1`, see if the left and upper borders have length at least `l`.\n\nFinally return the longest border length. One for loop block is enough, as for each `i, j`, we have full informations for left and upper directions.\n\n```\n* row[][]: max len with 1 till i\n* col[][]: max len with 1 till j\n//\n// For l = 4, 3, 2, 1, see if the left and upper borders are valid.\n//  1      1      1     [1] (i, j - l + 1)\n//\n//  1                    1\n//      \n//  1                    1\n//\n// [1]    1      1      [1] (i, j)     \n//\uFF08i - l + 1, j)      \n\n```\nCode is straightforward:\n```\nclass Solution {\n    public int largest1BorderedSquare(int[][] grid) {\n        int m = grid.length, n = grid[0].length;\n        int[][] row = new int[m][n], col = new int[m][n];\n        int res = 0;\n        for (int i = 0; i < m; i++) {\n            for (int j = 0; j < n; j++) {\n                if (grid[i][j] == 1) {\n                    row[i][j] = j >= 1 ? row[i][j - 1] + 1 : 1;\n                    col[i][j] = i >= 1 ? col[i - 1][j] + 1 : 1;\n                }\n\n                int len = Math.min(row[i][j], col[i][j]);\n                for (int l = len; l >= 1; l--) {\n                    if (row[i - l + 1][j] >= l && col[i][j - l + 1] >= l) {\n                        res = Math.max(res, l * l);\n                        break;\n                    }\n                }\n            }\n        }\n        return res;\n    }\n}\n```
['Java']