# Maximal-Square

Nov 16, 2017

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.

def expend(self,matrix,i,j,ret):
"""
:type matrix: List[List[str]]
:type i: int
:type j: int
:type ret: int
:rtype ret
"""
if i >= len(matrix) or j >= len(matrix[0]):
return ret
for k in range(ret+1):
if matrix[i][j - k] == '0' or matrix[i-k][j] == '0':
return ret
return self.expend(matrix,i+1,j+1,ret+1)

def maximalSquare1(self, matrix):
"""
:type matrix: List[List[str]]
:rtype: int
"""
ret,i = 0,0
while i + ret < len(matrix):
j = 0
while j + ret < len(matrix[0]):
if matrix[i][j] == '1':
ret = max(ret,self.expend(matrix,i+1,j+1,1))
j += 1
i += 1
return ret*ret

[
[1,1,*]
[1,1,*]
[*,*,-]
]

[
[*,*,*]
[1,1,*]
[1,1,-]
]

[
[*,1,1]
[*,1,1]
[*,*,-]
]

size[i][j] = min(size[i-1][j-1],size[i][j-1],size[i-1][j])+1 if matrix[i][j] == '1' size[i][j] = 0 if matrix[i][j] == '0'

size[i][j] = (matrix[i][j] == '1') where i == 0 or j == 0

def maximalSquare(self,matrix):
if len(matrix) == 0:
return 0
dp1 = []
ret = 0
for i in range(len(matrix[0])):
t = int(matrix[0][i] == '1')
dp1.append(t)
ret = max(ret,t)
for i in range(1,len(matrix)):
dp2 = [ 0 for i in range(len(matrix[0])) ]
dp2[0] = int(matrix[i][0] == '1')
ret = max(dp2[0],ret)
for j in range(1,len(matrix[0])):
if matrix[i][j] == '1':
dp2[j] = min(min(dp1[j-1],dp1[j]),dp2[j-1]) + 1
ret = max(ret,dp2[j])
dp1 = dp2
return ret*ret
LeetCodeDP

Implement Trie(Prefix Tree)

Best Time to Buy and Sell Stock