Maximal Square

221. Maximal Square

Solution

Reference

1. Keep the length of the square instead of the area.

2. The length of a square depends on the 3 girds which are neighbors to it. The smallest decides its length.

   def maximalSquare(self, matrix):
    """
    :type matrix: List[List[str]]
    :rtype: int
    """
    if matrix is None or len(matrix) == 0:
        return 0
       
    res = 0
    prev = [0] * (len(matrix[0]) + 1)
    for i in range(len(matrix)):
        curr = [0] * (len(matrix[0]) + 1)
        for j in range(len(matrix[0])):
            if matrix[i][j] == '1':
                curr[j+1] = min(curr[j], prev[j+1], prev[j]) + 1
                res = max(res, curr[j+1])
        prev = curr
    return res ** 2