Maximal Rectangle

Pre requisite: Maximum Area Histogram

Problem Link: https://leetcode.com/problems/maximal-rectangle/

class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        
        def maxAreaHistogram(nums):
            
            nsl=[]
            nsr=[]
            n=len(nums)
            s=[]
            for i in range(n):
                if(len(s)==0):
                    nsl.append(-1)
                else:
                    if(nums[s[-1]]<nums[i]):
                        nsl.append(s[-1])
                    else:
                        while(len(s)>0 and nums[s[-1]]>=nums[i]):
                            s.pop()
                        if(len(s)==0):
                            nsl.append(-1)
                        else:
                            nsl.append(s[-1])
                s.append(i)
            
            s=[]
            for i in range(n-1,-1,-1):
                if(len(s)==0):
                    nsr.append(n)
                else:
                    if(nums[s[-1]]<nums[i]):
                        nsr.append(s[-1])
                    else:
                        while(len(s)>0 and nums[s[-1]]>=nums[i]):
                            s.pop()
                        if(len(s)==0):
                            nsr.append(n)
                        else:
                            nsr.append(s[-1])
                s.append(i)
            nsr=nsr[::-1]
            
            ans=0
            for i in range(n):
                ans=max(ans,(nsr[i]-nsl[i]-1)*nums[i])
            
            return ans
        
        ans=0
        rows=len(matrix)
        columns=len(matrix[0])
        for i in range(rows):
            for j in range(columns):
                if(i==0):
                    matrix[i][j]=int(matrix[i][j])
                else:
                    if(matrix[i][j]!='0'):
                        matrix[i][j]=int(matrix[i-1][j])+1
                    else:
                        matrix[i][j]=int(matrix[i][j])
            ans=max(ans,maxAreaHistogram(matrix[i]))

        return ans