Python O(N^3) time complexity with graphic illustration
At each point that is not 0, we try to construct the largest square that uses the point as the lower right corner that satisties the condition.\n\nConsider the 
At each point that is not `0`, we try to construct the largest square that uses the point as the lower right corner that satisties the condition.\n\nConsider the point at `(3, 3)`, highlighted in red below. We first find how many `1` are above it (including itself, and how many `1` are on its left, including itself. In this case, we have 4 above and 4 on the left. The largest possible square we can construct here is capped by the minimum of the two numbers, `min(4, 4) = 4`.\n\n![image](https://assets.leetcode.com/users/basi4869/image_1564288832.png)\n\nNext, we go try out these 4 possibilities, starting from the largest. So we try the following 4 green corners, starting from the furthest one from our red point. When we try these green points, we are interested in whether there are enough `1` on the right and below the green point to complete a square with the beams extended from the red point. This condition is that **the minimum between the numbers of 1\'s on the right and below the green point is greater than or equal to the distance between the green and the red points**.\n\n![image](https://assets.leetcode.com/users/basi4869/image_1564289677.png)\n\nTry the first one, its distance from the red point is 4, there is 0 on its right and 0 below it. `min(0, 0) < 4`, so not valid.\n\n![image](https://assets.leetcode.com/users/basi4869/image_1564289692.png)\n\nTry the second one, its distance from the red point is 3, there is 4 on its right and 8 below it. `min(4, 8) >= 3`. So we have found a square of size `3*3`.\n\n![image](https://assets.leetcode.com/users/basi4869/image_1564289686.png)\n\n![image](https://assets.leetcode.com/users/basi4869/image_1564289699.png)\n\nTo facilitate this process, I first find how many 1s are above, below, on the left, and on the right of each point, including the point itself.\n\n```python\nclass Solution:\n    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n        \n        R, C = len(grid), len(grid[0])\n        up = [[0 for _ in range(C)] for _ in range(R)]\n        down = [[0 for _ in range(C)] for _ in range(R)]\n        left = [[0 for _ in range(C)] for _ in range(R)]\n        right = [[0 for _ in range(C)] for _ in range(R)]\n        \n        for r in range(R):\n            for c in range(C):\n                if r == 0:\n                    up[r][c] = grid[r][c]\n                else:\n                    up[r][c] = grid[r][c] + up[r-1][c] if grid[r][c] == 1 else 0\n        \n        for r in range(R-1, -1, -1):\n            for c in range(C):\n                if r == R-1:\n                    down[r][c] = grid[r][c]\n                else:\n                    down[r][c] = grid[r][c] + down[r+1][c] if grid[r][c] == 1 else 0\n        \n        for c in range(C):\n            for r in range(R):\n                if c == 0:\n                    left[r][c] = grid[r][c]\n                else:\n                    left[r][c] = grid[r][c] + left[r][c-1] if grid[r][c] == 1 else 0\n        \n        for c in range(C-1, -1, -1):\n            for r in range(R):\n                if c == C-1:\n                    right[r][c] = grid[r][c]\n                else:\n                    right[r][c] = grid[r][c] + right[r][c+1] if grid[r][c] == 1 else 0\n        \n        res = 0\n        \n        for r in range(R):\n            for c in range(C):\n                if grid[r][c] == 0:\n                    continue\n                side = min(up[r][c], left[r][c])\n                for i in range(side-1, -1, -1):\n                    if i < res:\n                        break\n                    if min(down[r-i][c-i], right[r-i][c-i]) >= i + 1:\n                        res = max(res, i + 1)\n                        break\n        return res * res\n```\n\n                    \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n
[]