Leetcode 221: Maximal Square

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Code

class Solution(object):
    def maximalSquare(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        if not matrix:
            return 0
        
        # convert to integer matrix
        for i in xrange(len(matrix)):
            for j in xrange(len(matrix[0])):
                matrix[i][j] = int(matrix[i][j])
            
        max_size = max(matrix[0])
        # DP storage initialized with the first row of matrix
        vec = list(matrix[0])
        
        for row in xrange(1, len(matrix)):
            topleft = vec[0]
            vec[0] = matrix[row][0]
            
            for col in xrange(1, len(matrix[0])):
                if matrix[row][col] == 0:
                    new = 0
                else:
                    new = min(topleft, vec[col-1], vec[col]) + 1
                topleft = vec[col]
                vec[col] = new
            
            max_size = max(max_size, max(vec))
                
        return max_size * max_size
        
        
        

Idea

Think about it as a 2D DP problem. Suppose a list vec has size num_row * num_col. vec[i][j] is the size of the maximum square that can be achieved at matrix[i][j]. The core logic is that vec[i][j] = min(vec[i][j-1], vec[i-1][j],vec[i-1][j-1]). 

And we know that 2D DP problem can often be reduced to 1D. That’s how I implement currently.

Reference:

https://discuss.leetcode.com/topic/15328/easy-dp-solution-in-c-with-detailed-explanations-8ms-o-n-2-time-and-o-n-space