#85

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Maximal Rectangle

Compute the largest rectangle of 1's in a binary matrix using dynamic programming and stack-based state transitions efficiently.

array dynamic programming stack matrix monotonic stack

Problem Statement

Given a rows x cols binary matrix filled with '0's and '1's, find the area of the largest rectangle containing only '1's. Each row contributes to the dynamic state, and you must calculate heights and boundaries cumulatively to identify maximal sub-rectangles efficiently. Optimizing these updates avoids unnecessary re-computation of every submatrix and leverages stack properties.

Return the maximal area as an integer. For example, with matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]], the largest rectangle consists of 6 contiguous '1's forming a 2x3 block. Edge cases include single-row, single-column, or all-zero matrices, which must return correct maximal areas. Ensure each row update respects previous state transitions for correctness.

Examples

Example 1

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]

Output: 6

The maximal rectangle is shown in the above picture.

Example 2

Input: matrix = [["0"]]

Output: 0

Example details omitted.

Example 3

Input: matrix = [["1"]]

Output: 1

Example details omitted.

Constraints

rows == matrix.length
cols == matrix[i].length
1 <= row, cols <= 200
matrix[i][j] is '0' or '1'.

Solution Approach

Dynamic Height Computation

Track a height array representing the number of consecutive '1's in each column up to the current row. For each row, increment the height if the cell is '1' or reset to zero if '0'. This converts the 2D matrix problem into a series of histogram problems, enabling the use of maximal rectangle logic row by row, which is central to the state transition dynamic programming approach for this problem.

Monotonic Stack for Width Boundaries

Maintain stacks to compute the nearest smaller elements on left and right for each histogram row derived from heights. This identifies the width boundaries of the largest rectangle that can be formed at each column. The monotonic stack ensures linear-time computation per row, avoiding repeated scanning and reducing the complexity from naive approaches that check every possible rectangle.

Cumulative Area Calculation

Using the computed heights and left-right boundaries for each row, calculate the area as height times width. Update a global maximal area variable after processing each row. This ensures that rectangles spanning multiple rows are correctly considered, leveraging previous rows' state transitions without redundant recalculation, and adheres strictly to the DP pattern essential for this maximal rectangle problem.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(rows * cols) due to iterating each cell once for height calculation and using stacks per row, while the space complexity is O(cols) for height, left, and right arrays. This ensures both time and space remain efficient even for large 200x200 matrices, matching the problem's constraints and DP pattern usage.

What Interviewers Usually Probe

Do you recognize how row-by-row state transitions reduce redundant computations?
Can you apply a monotonic stack to track maximal rectangle boundaries efficiently?
Will you update height, left, and right arrays correctly for each row to compute areas?

Common Pitfalls or Variants

Common pitfalls

Failing to reset height to zero for '0' cells leads to incorrect cumulative heights.
Incorrectly computing left and right boundaries can result in underestimating maximal rectangle width.
Assuming maximal rectangle always starts at the first '1' without proper DP tracking misses valid areas spanning multiple rows.

Follow-up variants

Compute maximal square instead of rectangle using similar height tracking DP.
Find the largest rectangle of 1's in a circular matrix wrapping rows or columns.
Return coordinates of the maximal rectangle instead of just its area.

FAQ

What is the main pattern used in Maximal Rectangle?

The problem follows state transition dynamic programming, where each row's heights and boundaries are updated cumulatively to find the maximal rectangle efficiently.

How do left and right arrays contribute to the solution?

Left and right arrays track the nearest smaller elements on each side for every column, defining the maximal width of a rectangle at each position and ensuring accurate area calculation.

Can this solution handle single-row or single-column matrices?

Yes, by updating height arrays row by row and using the same boundary logic, single-row or single-column matrices are correctly processed without extra special cases.

Why is a monotonic stack important in this problem?

Monotonic stacks allow linear-time computation of nearest smaller elements, which define width boundaries for rectangles and prevent O(n^2) scanning across columns.

What is the time and space complexity for Maximal Rectangle?

The time complexity is O(rows*cols) because each cell is visited once, and the space complexity is O(cols) for height, left, and right arrays.

terminal

Solution

Solution 1: Monotonic Stack

We can treat each row as the base of a histogram and calculate the maximum area of the histogram for each row.

class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        heights = [0] * len(matrix[0])
        ans = 0
        for row in matrix:
            for j, v in enumerate(row):
                if v == "1":
                    heights[j] += 1
                else:
                    heights[j] = 0
            ans = max(ans, self.largestRectangleArea(heights))
        return ans

    def largestRectangleArea(self, heights: List[int]) -> int:
        n = len(heights)
        stk = []
        left = [-1] * n
        right = [n] * n
        for i, h in enumerate(heights):
            while stk and heights[stk[-1]] >= h:
                stk.pop()
            if stk:
                left[i] = stk[-1]
            stk.append(i)
        stk = []
        for i in range(n - 1, -1, -1):
            h = heights[i]
            while stk and heights[stk[-1]] >= h:
                stk.pop()
            if stk:
                right[i] = stk[-1]
            stk.append(i)
        return max(h * (right[i] - left[i] - 1) for i, h in enumerate(heights))

Continue Practicing

#42 trapping rain water #1504 count submatrices with all ones #907 sum of subarray minimums