Maximal Rectangle

Problem Id: 85 Difficulty: Hard Tag: Array Tag: Hash Table Tag: Dynamic Programming Tag: Stack


Intuition

We could handle it by rows.

In each row, it is easily to get the maximum height of the current column by DP. Because dp[i][j] = dp[i - 1][j] + 1 if matrix[i][j] is 1, else it is 0.

With this dp array, we could use the algorithm we used in problem <85. Largest Rectangle in Histogram> to get the maximum area of the rectangle ends with each node.

Solution


class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if not matrix or not matrix[0]:
            return 0
        m, n = len(matrix), len(matrix[0])
        dp = [0] * (n + 1)
        max_area = 0
        for i in range(m):
            # Use DP to get the height of each column
            for j in range(n):
                if matrix[i][j] == "1":
                    dp[j] += 1
                else:
                    dp[j] = 0

            # Use stack to get the maximum area
            stack = [[-1, -1]]
            for index, height in enumerate(dp):
                i = index
                while stack[-1][0] >= height:
                    h, i = stack.pop()
                    area = h * (index - i)
                    max_area = max(area, max_area)
                stack.append([height, i])
        return max_area