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

30 days! Lets go Lets go!
N2I -2020.04.28

1. My solution

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

Explanation:

It is a bit busy these days. I’ll find some time to add the explanation here.

2. A better Solution

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

Explanation:

It is a bit busy these days. I’ll find some time to add the explanation here.