[Java] Two solutions explained. O(n³) time and O(1) space
Simple O(n\u2074) solution passes in 450 ms. Idea is following:\nIterate over possible length O(n)\nIterate over possible starting position O(n\xB2)\nCheck if p
Simple `O(n\u2074)` solution passes in 450 ms. Idea is following:\nIterate over possible length `O(n)`\nIterate over possible starting position `O(n\xB2)`\nCheck if possition is valid for given length `O(n)`\nOverall `O(n\u2074)` and `O(1)` space\n\n```\nclass Solution {\n    public int largest1BorderedSquare(int[][] grid) {\n        int n = grid.length;\n        int m = grid[0].length;\n        for (int length = Math.min(n, m); length > 0; length--) {\n            for (int i = 0; i + length <= n; i++) {\n                for (int j = 0; j + length <= m; j++) {\n                    boolean flag = true;\n                    \n                    for (int g = 0; g < length; g++) {\n                        flag &= grid[i + g][j] == 1;\n                        flag &= grid[i + g][j + length - 1] == 1;\n                        \n                        flag &= grid[i][j + g] == 1;\n                        flag &= grid[i + length - 1][j + g] == 1;\n                    }\n                    \n                    if (flag) {\n                        return length * length;\n                    }\n                }\n            }\n        }\n        \n        return 0;\n    }\n}\n```\n\nWe can improve our solution with following idea:\nFor each cell `grid[i][j]` we should maintain number of `1` above and number of `1` to the left. With this information we can check if subgrid is valid in `O(n\xB3)` time.\nWe can even simplify our solution to use `O(1)` space by using input array for precomputing.\nThis solution runs in 3 ms\n\n```\nclass Solution {\n    public int largest1BorderedSquare(int[][] grid) {\n        int n = grid.length;\n        int m = grid[0].length;\n        \n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < m; j++) {\n                if (grid[i][j] == 0)\n                    continue;\n                \n                int left = 1;\n                if (j > 0) {\n                    left = grid[i][j - 1] % 1000 + 1;\n                }\n                \n                int top = 1;\n                if (i > 0) {\n                    top = grid[i - 1][j] / 1000 + 1;\n                }\n                \n                grid[i][j] = left + top * 1000;\n            }\n        }\n        \n        int answer = 0;\n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < m; j++) {\n                int length = Math.min(grid[i][j] % 1000, grid[i][j] / 1000);\n                \n                for (int g = answer; g < length; g++) {\n                    if (grid[i][j - g] / 1000 > g && grid[i - g][j] % 1000 > g) {\n                        answer = Math.max(answer, g + 1);\n                    }\n                }\n            }\n        }\n        \n        return answer * answer;\n    }\n}\n```
[]