Stack • Hard Problems

Maximal Rectangle in 2D Matrix

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

Connection to Histograms

This problem is a direct extension of "Largest Rectangle in Histogram". We can treat every row in the matrix as the base of a histogram!

Building Heights

As you iterate down the matrix row by row, maintain an array of `heights`. If the cell is '1', increment its height. If it is '0', reset its height to 0.

O(N x M) Solution

For each row, run the O(N) Monotonic Stack algorithm from "Largest Rectangle in Histogram" on the updated `heights` array. Keep a running maximum of the area found across all rows.

Loading Lab...

Stack • Hard Problems

Maximal Rectangle in 2D Matrix

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

Connection to Histograms

This problem is a direct extension of "Largest Rectangle in Histogram". We can treat every row in the matrix as the base of a histogram!

Building Heights

As you iterate down the matrix row by row, maintain an array of `heights`. If the cell is '1', increment its height. If it is '0', reset its height to 0.

O(N x M) Solution

For each row, run the O(N) Monotonic Stack algorithm from "Largest Rectangle in Histogram" on the updated `heights` array. Keep a running maximum of the area found across all rows.