[Python3] Prefix Sum Solution
Code\n\nclass Solution:\n    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n        m = len(grid)\n        n = len(grid[0])\n\n        horiPre
# Code\n```\nclass Solution:\n    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n        m = len(grid)\n        n = len(grid[0])\n\n        horiPrefix = [[0 for j in range(n)] for i in range(m)]\n        vertiPrefix = [[0 for j in range(n)] for i in range(m)]\n\n        for i in range(m):\n            for j in range(n):\n                if grid[i][j]==1:\n                    horiPrefix[i][j] = (horiPrefix[i][j-1] if j-1>=0 else 0) + grid[i][j]\n\n        for j in range(n):\n            for i in range(m):\n                if grid[i][j]==1:\n                    vertiPrefix[i][j] = (vertiPrefix[i-1][j] if i-1>=0 else 0) + grid[i][j]\n        \n        ans = 0\n        for i in range(m):\n            for j in range(n):\n                possibleLen = min(i,j)+1\n                for l in range(1, possibleLen+1):\n                    if horiPrefix[i][j]>=l and vertiPrefix[i][j]>=l and horiPrefix[i-l+1][j]>=l and vertiPrefix[i][j-l+1]>=l:\n                        ans = max(ans, l*l)\n                    \n        return ans\n```
['Python3']