Python solution with detailed explanation


  • 0
    G

    Solution

    Maximal Rectangle https://leetcode.com/problems/maximal-rectangle/

    Algorithm

    • Review the solution for https://leetcode.com/problems/largest-rectangle-in-histogram/
    • The solution is based on largest rectangle in histogram solution. Every row in the matrix is viewed as the ground with some buildings on it. The building height is the count of consecutive 1s from that row to above rows. The rest is then the same as this solution for largest rectangle in histogram
    • heights[j] = heights[j] + int(matrix[i][j]) if int(matrix[i][j]) else 0 - makes sure we reset the count when we have a zero.
    class Solution(object):
        def largestRectangleArea(self, heights):
            max_area, st = 0, []
            for idx,x in enumerate(heights):
                if len(st) == 0:
                    st.append(idx)
                elif x >= heights[st[-1]]:
                    st.append(idx)
                else:
                    while st and heights[st[-1]] > x:
                        min_height = heights[st.pop()] 
                        max_area = max(max_area, min_height*(idx-1-st[-1])) if st else max(max_area, min_height*idx)
                    st.append(idx)
            while st:
                min_height = heights[st.pop()] 
                max_area = max(max_area, min_height*(len(heights)-1-st[-1])) if st else max(max_area, min_height*len(heights))
            return max_area
            
        def maximalRectangle(self, matrix):
            """
            :type matrix: List[List[str]]
            :rtype: int
            """
            if matrix == []:
                return 0
            N, M = len(matrix), len(matrix[0])
            max_area, heights = 0, [0]*M
            for i in range(N):
                for j in range(M):
                    heights[j] = heights[j] + int(matrix[i][j]) if int(matrix[i][j]) else 0
                max_area = max(max_area, self.largestRectangleArea(heights))
            return max_area
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.