Python3: FT 100%: TC O(M^2 N), SC O(M N): Mostly DP with a Few Optimizations
Intuition\n\nFor most problems involving squares or sides in grids, we usually need to know the number of consecutive ones. We can do this with O(M N) DP.\n\nIn
# Intuition\n\nFor most problems involving squares or sides in grids, we usually need to know the number of consecutive ones. We can do this with O(M N) DP.\n\nIn this case, 1-bordered squares mean we need to find cells with a specific number of consecutive 1s down and to the right. So we\'re probably on the right track.\n\nIn more detail: to form a 1-bordered region of size `k x k` with the upper-left corner at `r, c` we need\n* at `r, c`: `k` consecutive 1\'s going down\n* at `r, c`: `k` consecutive 1\'s going right\n* at `r+k-1, c`: `k` consecutive 1\'s going right\n* at `r, c+k-1`: `k` consecutive 1\'s going down\n\nHere\'s some ASCII art:\n```a\n   (r,c)     k ones\n       \\  --------->\n k    |  1  1  1  1  |\nones  |  1        1  | k ones\n      |  1        1  |\n      |  1  1  1  1  V\n       ------------>\n           k ones\n```\n\nAt `r,c`:\n* suppose we have `D` 1s going down\n* and we have `R` 1s going right\n* then the largest *square* we can form has side length `min(D,R)`\n* so we know the largest side length to check\n\nWe can use DP to get the consecutive ones in both directions. Then we can iterate over the grid and find the largest square with each upper-left coordinate. The best answer is the max square size over all (r,c) starting locations (i.e. all O(M N) choices for the upper-left).\n\n# Approach\n\n## Consecutive Ones Down and Left\n\nA (somewhat) common DP operation for grids is getting the number of consecutive ones in some direction. This shows up in a lot of "skyline" problems too, or places where you need to quickly get information about consecutive elements meeting some criterion.\n\nFor consecutive ones going right:\n* if the right-most element is 0, the count is zero\n* if the right-most element is 1, the count is one\n* for each r < R-1\n  * if the current element is 1, the count is 1 plus the number of consecutive ones starting one element to the right: we take the `k` 1\'s off to the right, and add 1 for the current element\n  * if the current element is 0, the count is 0\n\nSome more ASCII art to explain what we\'re doing:\n```\nrow:                        0 1 1 1 0 0 1 1 0 1 1 1 1 0\nconsecutive ones to right:  0 3 2 1 0 0 2 1 0 4 3 2 1 0\n```\n\nThe same logic applies to consecutive ones downward, but with rows/columns flipped. Same idea, just be careful about R vs. C.\n\n## Main Loop\n\nFor all `r,c` coordinates, we can find the max edge length using `min(down[r][c], right[r][c])`. Any edge longer than that will have a zero along at least one edge, or go out of bounds.\n\nThen for each possible side length `l`, we check\n* if we go the bottom-left corner, are there `l` ones to the right?\n* if we go to the top-right corner, are there `l` ones going down?\n\nIf the answer to both is yes, then we have a square of side length `l`.\n\n## Optimizations\n\nWe want the cumulative max over all starting locations. Therefore we only care about improving the current max.\n\n### Early Break in R/C Loops\n\nIf we\'re at (r,c) and the current best side length is `best`, then a new best square would end at least at `r+best+1-1, c+best+1-1 == r+best, c+best`.\n\nIf those coordinates are out of bounds, we can\'t possibly improve on the best. So I added an early `break` statement to the outermost loop (rows), and adjusted the upper bound of the inner loop (cols).\n\n### Try Longest First\n\nSince we want the maximum, we don\'t care about *all* the edge lengths we can form at `r,c` - we just want the max. So I iterate from the longest length downward, and break if/when we get a length. This way we look at the fewest squares possible.\n\n### Only Try Larger Squares\n\nSimilar to "Try Longest First," we know that the only squares that can improve the current `best` have side length `best+1` or longer.\n\nSo I only check lengths from `longest` to `best+1` in descending order. If we find a square, we know this is a new best (because we *only* consider lengths that will be a new best) so we set `best = l` directly.\n\n# Complexity\n- Time complexity: O(M^2 N)\n  - M is the shorter axis\n  - N is the longer axis\n  - analysis: we do O(M N) iterations, over most upper-left coordintes `r, c`. In each iteration, we look at longest possible edge length, which is O(M). So we do O(M M N) work total.\n  - the `down` and `left` DP grids only take O(M N)\n\n- Space complexity: O(M N) because we form `down` and `right` DP grids\n\nIn practice I think the complexity is typically lot lower because we only iterate over lengths from `min(down[r][c], right[r][c])` down to `best+1`\n* for early r,c coordinates, usually one axis will have many fewer consecutive ones than the other. The worst case would be a lot of downward and rightward lines of 1s\n* for later r,c coordinates, the current best increases so the number of side lengths we check decreases\n* for very late r,c coordintes, given the current best, we skip checking late r and c values entirely\n\nSo the effective size of the grid decreases over time, and the range of the loop decreases over time. If there\'s a large rectangle early then the "Only Try Larger Rectangles" optimization means we don\'t actually iterate over any candidate squares at all.\n\n# Code\n```\nclass Solution:\n    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n        R = len(grid)\n        C = len(grid[0])\n\n        # want largest square subgrid: min(R,C) side length\n        # max(R,C)-min(R,C)+1 different offsets in other direction\n\n        # Reread problem, a lot easier than I thought (we\'re not counting\n        # number of 1-bordered squares in the largest square) - we want\n        # the size of the largest 1-bordered square\n\n        # the grid already gives us the size of 1x1 squares\n        # DP?\n        #    for x 1 1 1 1 1\n        #        1     1\n        #        1     1\n        #        1 1 1 1       4x4\n\n        # if we knew\n        #   x has 6 left and 4 down ones, including x\n        #   So max grid size at x is 4x4\n        #   We can look at right[x + (3,0)] -> get 4\n        #   and look at down[x + (0,3)] -> get 4\n        # so we have a 4x4\n\n        # For a MxN grid, the max number of 1s at any cell would be O(M) down and O(N) right\n        # for each one we\'d do O(min(M,N)) ops\n        # so if shorter axis is M and longer is N, then we\'d do O(MN) iterations, and O(M) ops per iteration\n        \n        # Can we go faster? I don\'t think so, but I have no proof.\n\n        # foo[r][c] is number of consec. 1s, including (r,c),  right/down starting at (r,c)\n        right = [[0]*C for _ in range(R)]\n        down = [[0]*C for _ in range(R)]\n\n        for r in range(R):\n            right[r][C-1] = grid[r][C-1]\n            for c in range(C-2, -1, -1):\n                if grid[r][c]:\n                    right[r][c] = right[r][c+1] + 1\n                # else: leave it zero\n\n        for c in range(C):\n            down[R-1][c] = grid[R-1][c]\n            for r in range(R-2, -1, -1):\n                if grid[r][c]:\n                    down[r][c] = down[r+1][c] + 1\n\n        L = min(R,C)\n        best = 0\n        for r in range(R):\n            # break early if we can\'t improve on the best; new best would need row index >= r+(best+1)-1\n            if r+best >= R: break\n            for c in range(C-best):\n                longest = min(down[r][c], right[r][c])\n                # only candidates > best can change the answer\n                for l in range(longest, best, -1):\n                    if right[r+l-1][c] >= l and down[r][c+l-1] >= l:\n                        best = l\n                        break\n        \n        return best**2 # FIX: area, not side length\n```
['Python3']