[python3] illustrated explanation
\n\n\n\n\ndef largest1BorderedSquare(self, grid: List[List[int]]) -> int:  # pylint: disable=invalid-name\n        """ O(N^3)T  O(N^2)S """\n        size_y, siz
![image](https://assets.leetcode.com/users/images/a06e8d5c-19b0-47a5-b6f6-395b8d7f6815_1595667282.729967.png)\n\n![image](https://assets.leetcode.com/users/images/0539507b-efc7-407a-a7b4-1026282fbb57_1595667296.5895104.png)\n\n```\ndef largest1BorderedSquare(self, grid: List[List[int]]) -> int:  # pylint: disable=invalid-name\n        """ O(N^3)T  O(N^2)S """\n        size_y, size_x, size_max, largest = len(grid), len(grid[0]), max(len(grid), len(grid[0])), 1 if sum(itertools.chain.from_iterable(grid)) > 0 else 0 #for 1-size square\n        prefixes = [[(0, 0)] * (size_x + 1) for _ in range(size_y + 1)]\n\n        # precompute row,column prefix summs\n        for y, row in enumerate(grid, start=1):\n            for x, num in enumerate(row, start=1):\n                (prev_y, _), (_, prev_x) = prefixes[y - 1][x], prefixes[y][x - 1]\n                prefixes[y][x] = (1 + prev_y, 1 + prev_x) if grid[y - 1][x - 1] else (prev_y, prev_x)\n\n        def check_square(x1, y1, x2, y2):  # [x1:x2] [y1:y2]\n            nonlocal largest\n            if not (0 <= x1 < size_x) or not (0 <= x2 < size_x) or not (0 <= y1 < size_y) or not (0 <= y2 < size_y): # because grid may be not squared\n                return False\n\n            size, x1, y1, x2, y2 = x2 - x1 + 1, x1 + 1, y1 + 1, x2 + 1, y2 + 1\n            left_vertical = prefixes[y2][x1][0] - prefixes[y1 - 1][x1][0]\n            right_vertical = prefixes[y2][x2][0] - prefixes[y1 - 1][x2][0]\n            upper_gorizontal = prefixes[y1][x2][1] - prefixes[y1][x1 - 1][1]\n            lower_gorizontal = prefixes[y2][x2][1] - prefixes[y2][x1 - 1][1]\n\n            if left_vertical == right_vertical == upper_gorizontal == lower_gorizontal == size:\n                largest = max(largest, size) # find max square\n             \n\n        # check all squares\n        for size in range(2, size_max + 1):\n            for y, row in enumerate(grid):\n                for x, num in enumerate(row):\n                    check_square(x, y, x + size - 1, y + size - 1)\n\n        return largest * largest\n```
[]