221 Maximal Square
Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.
For example, given the following matrix:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Return 4.
The Idea: Harness the power of DP. Store the matrix as a submatrix of an n+1 larger matrix. Then, for each element in the submatrix, find the
min(left, right, diag) + 1. The above example will in effect become: 0 0 0 0 0 0
0 1 0 1 0 0
0 1 0 1 1 1
0 1 1 1 2 2
0 1 0 0 1 0
The intuition is that we want to find a way that tells us what size our square matrix is by looking it's surrounding neighbors. A 4 by 4 square for example, can become decomposed as follows:
0 0 0 0 0
0 1 1 1 1
0 1 2 2 2
0 1 2 3 3
0 1 2 3 4
Notice how every number is true for every subsquare in the matrix. Once we know what matrix we want to generate, we can reverse engineer a formula (
min(left, right, diag) + 1) that makes this true.Complexity: O(2n) time (extra time converting char matrix to int matrix) and O(1) space
import numpy as np
class Solution:
def maximalSquare(self, matrix):
"""
:type matrix: List[List[str]]
:rtype: int
"""
if not matrix:
return 0
Matrix = np.zeros((len(matrix) + 1, len(matrix[0]) + 1))
Matrix[1:Matrix.shape[0], 1:Matrix.shape[1]] = np.array(matrix, dtype=int)
the_max = 0
for i in range(1, Matrix.shape[0]):
for j in range(1, Matrix.shape[1]):
if Matrix[i][j] == 1:
Matrix[i][j] = min(Matrix[i - 1, j], Matrix[i - 1, j - 1], Matrix[i, j - 1]) + 1
the_max = max(the_max, int(Matrix[i][j]))
return the_max*the_max
t1 = [['1', '0', '1', '0', '0'],
['1', '0', '1', '1', '1'],
['1', '1', '1', '1', '1'],
['1', '0', '0', '1', '0']]
obj = Solution()
print(obj.maximalSquare(t1))
Last modified 4yr ago