Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.
Example:
Input: [ ["1","0","1","0","0"], ["1","0","1","1","1"], ["1","1","1","1","1"], ["1","0","0","1","0"] ] Output: 6
My code:
import numpy as np
class Solution:
def maximalRectangle(self, matrix):
"""
:type matrix: List[List[str]]
:rtype: int
"""
if len(matrix)==0:
return 0
self.m=len(matrix)
example=matrix[0]
if len(example)==0:
return 0
self.n=len(example)
self.matrix=np.zeros([self.m,self.n])-1
self.result=0
#Init self.matrix
for k in range(self.n):
if matrix[0][k]=='1':
self.matrix[0][k]=1
else:
self.matrix[0][k]=0
self.check_rec(matrix,self.m-1,self.n-1)
#print(self.matrix)
count=0
#special for first row
for k in range(self.n-1,-1,-1):
if matrix[0][k]=='1':
count+=1
self.result=max([self.result,count])
else:
count=0
return int(self.result)
def check_rec(self,matrix,i,j):
if i<0 or j<0:
return 0
if self.matrix[i][j]!=-1:
return self.matrix[i][j]
if matrix[i][j]=='1':
self.matrix[i][j]=1+self.check_rec(matrix,i-1,j)
self.result=max([self.result,self.matrix[i][j]])
height=self.matrix[i][j]
for k in range(j-1,-1,-1):
if self.check_rec(matrix,i,k)=='0':
break
height=min([height,self.check_rec(matrix,i,k)])
self.result=max([self.result,height*(j+1-k)])
return self.matrix[i][j]
else:
self.matrix[i][j]=0
self.check_rec(matrix,i,j-1)
self.check_rec(matrix,i-1,j)
return self.matrix[i][j]
Solution: https://leetcode.com/problems/maximal-rectangle/submissions/