Leetcode 221. Maximal Square (Python)

Related Topic

Dynamic-Programming.

Description

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.

Sample I/O

Example 1

Input: 

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

Output: 4

Methodology

This question can be solved by Dynamic Programming. However there are various way to implement DP.

To find the maxmium square, we need to find square first. 1 is a square with length equal to 1. Any square with length more than 2 can be made of square with length 2.

Find the base case:

If there is 1 exist in the given input, then there is at least 1 square and the area is 1.

Find the pattern:

If any element equal to 1 then we check its left, right and upper left element if they are all greater than 1 then we know there is at least a square with length greater than 1. we need to find the minimum from it’s left, right and upper then + 1 to get the current square’s length. If the square is greater the maximum square then we update the maximum square.

Answer:

maximum square variable

Code

def maximalSquare(self, matrix: List[List[str]]) -> int:
        if not matrix: return 0
        R = len(matrix)
        C = len(matrix[0])
        dp = [[0]*C for _ in range(R)]
        mx_count = 0
        for i in range(R):
            for j in range(C):
                dp[i][j] = int(matrix[i][j])
                if dp[i][j]: mx_count = 1
        for i in range(1,R):
            for j in range(1,C):
                if dp[i][j] and dp[i-1][j] and dp[i][j-1] and dp[i-1][j-1]:
                    dp[i][j] = min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1
                    mx_count = dp[i][j] if dp[i][j]>mx_count else mx_count
        return mx_count**2

BigO

Create dp list will cost O(n^2) and iterate the dp will cost (n^2) in total will be O(2n^2)