[LeetCode][python3]Day27. Maximal Square (30-Day LeetCoding Challenge)

class Solution:
def maximalSquare(self, matrix: List[List[str]]) -> int:
self.one=set()
one=self.one
res=0
for row in range(len(matrix)):
for col in range(len(matrix[0])):
if matrix[row][col]=="1":
one.add((row,col))
res=max(res,self.check(row,col,res))
#print(one)
return res*res
def check(self,row,col,res):
one=self.one
for i in range(res+1):
for j in range(i+1):
if (row-i,col-i+j) not in one or (row-i+j,col-i) not in one:
#print('res=',res,'i,j=',i,j,'(x,y)=',row,col)
#print(one)
return i
#print('res=',res,'i=',i,'(x,y)=',row,col)
#print(one)
return res+1
class Solution:
def maximalSquare(self, matrix: List[List[str]]) -> int:
if not matrix:
return 0
m, n = len(matrix), len(matrix[0])
heights = [0] * n
max_width = 0
for i in range(m):
width = 0
for j in range(n):
# populates heights arr
if matrix[i][j] == '1':
heights[j] += 1
else:
heights[j] = 0
# calculates max square width using greedy approach
if heights[j] > max_width:
width += 1
if width > max_width:
max_width, width = width, 0
else:
width = 0
return max_width * max_width

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store