1139.md

1139. Largest 1-Bordered Square

Solution 1 (time O(mnmin(m,n)), space O(m*n))

class Solution(object):
    def largest1BorderedSquare(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        m, n = len(grid), len(grid[0])
        dp = [[[0 for _ in range(2)] for _ in range(n)] for _ in range(m)]
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    if j == 0:
                        dp[i][j][0] = 1
                    else:
                        dp[i][j][0] = dp[i][j - 1][0] + 1
                    if i == 0:
                        dp[i][j][1] = 1
                    else:
                        dp[i][j][1] = dp[i - 1][j][1] + 1
        max_length = 0
        for i in range(m):
            for j in range(n):
                cur_length = min(dp[i][j][0], dp[i][j][1])
                if cur_length <= max_length:
                    continue
                while cur_length > max_length:
                    if dp[i][j - cur_length + 1][1] >= cur_length and dp[i - cur_length + 1][j][0] >= cur_length: 
                        max_length = cur_length
                        break
                    cur_length -= 1
        return max_length * max_length