Algorithm

Maximal Rectangle

Monotonic Stack Pattern

Maximal Rectangle

Given a rows x cols binary matrix filled with '0's and '1's, find the largest rectangle containing only '1's and return its area.

CONSTRAINTS
  • rows == matrix.length
  • cols == matrix[i].length
  • 1 <= rows, cols <= 200
  • matrix[i][j] is '0' or '1'
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 central 3x2 block of ones at indices (1,2) to (2,4) forms the largest rectangle.
Do we need the logic from Largest Rectangle in Histogram?
Yes. This problem is effectively a 'wrapper' around the histogram problem. The core observation is that a 2D matrix of ones is just a set of stacked histograms.

Finding the largest rectangle in a 2D matrix of ones and zeros feels much harder than any 1D problem. But there is a brilliant way to "flatten" this challenge into something we have already solved: the Largest Rectangle in Histogram.

The Skyline Discovery

Imagine you are standing on the first row of the matrix. Every "1" in that row acts like a building bar of height 1. This forms a 1D Histogram.
- Now, move down to the second row.
- If a column still has a "1", its building just grew by 1 floor. It is now 2 units high.
- If a column has a "0", the building is demolished! No record can stretch through a zero, so its height resets to 0.

By doing this "floor by floor," we can treat every single row of the matrix as the base of a brand new histogram. If we can find the Largest Rectangle in every row's histogram, the absolute maximum area we ever see is our global answer.

Reusing the Monotonic Stack

We maintain a heights array that we update as we move downward through the rows. After updating the heights for a specific row, we run the standard Largest Rectangle in Histogram algorithm (using a Monotonic Stack).

This solves the complex 2D geometry in linear time relative to the number of cells in the grid.

Code Blueprint
text
heights = [0] * cols
max_area = 0

FOR row in matrix:
    // 1. Update the Skyline (O(cols))
    FOR col_idx from 0 to cols-1:
        IF matrix[row][col_idx] == '1':
            heights[col_idx] += 1
        ELSE:
            heights[col_idx] = 0
            
    // 2. Solve the 1D problem for this row (O(cols))
    row_max = solve_largest_histogram(heights)
    max_area = MAX(max_area, row_max)

RETURN max_area
Worked Example:matrix = [['1','0','1'],['1','1','1']]
0
1
Row 0
1
0
2
1
Row 0 heights = [1, 0, 1]. Histogram max area for Row 0 is 1.
0
2
1
1
Row 1
2
2
Row 1 heights = [1+1, 0+1, 1+1] = [2, 1, 2]. Histogram max area is 3 (obtained by a rectangle of height 1 spanning all 3 columns). Max overall: 3.
Interactive Strategy Visualization
MATRIX REDUCTION INSIGHT

2D Matrix to Histogram Strategy

Processing Row 0
1
0
1
0
1
1
1
1
1
1
1
0
Histogram View
1
1

Key Strategy

1

Histogram Evolution: At each row, update heights based on consecutive 1s.

2

Monotonic Stack: Solve the Largest Rectangle in Histogram for each row.

Complexity
TimeO(N × M)
SpaceO(M)
TIP

Dynamic Reduction

The core insight is to transform the 2D grid problem into multiple 1D histogram problems. For each row, calculate how many consecutive '1's exist ending at that cell.

O((R × C)²) Brute Force
→
O(R² × C) Row Prefixes
→
O(R × C) Histogram + Monotonic Stack