[LeetCode] 85. Maximal Rectangle

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

This is an extended problem of 84. Largest Rectangle in Histogram

Scan "1" on each row and convert to histogram bars. Let every row as bottom of a histogram then calculate largest rectangle of each histogram.

class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        
        def largestRectangle(heights):
            """
            find largest rectangle of each histogram
            """
            result = 0
            stack = []
            
            for i in range(len(heights)):
                start = i
                h = heights[i]
                
                while stack and stack[-1][1] > h:
                    index, height = stack.pop()
                    
                    tmp = height * (i - index)
                    result = max(result, tmp)
                    
                    start = index
                
                stack.append((start, h))
            
            while stack:
                index, height = stack.pop()
                
                tmp = height * (len(heights) - index)
                result = max(result, tmp)
            
            return result     
        
        if not matrix:
            return 0
        
        row = len(matrix)
        column = len(matrix[0])
        
        heights = [0] * column
        
        result = 0
    
        for y in range(row):
            for x in range(column):
            	# convert "1" and "0" into bars
                if matrix[y][x] == "1":
                    heights[x] += 1
                else:
                    heights[x] = 0
                
            result = max(result, largestRectangle(heights))
        
        return result