Given a grid of 0s and 1s, find the largest rectangle containing only 1s. Return its area.
DSA Animator › DSA Revision › Stack › Maximal Rectangle
Remember: a 2D rectangle problem becomes a 1D histogram per row. Reuse the monotonic stack from problem 84. The video solves Maximal Rectangle (LeetCode 85, Hard) with the Histogram per Row pattern from the Stack topic, and you can replay every step in the interactive Maximal Rectangle animation.
Given a grid of 0s and 1s, find the largest rectangle containing only 1s. Return its area.
For this 4 by 5 grid, the largest all-ones rectangle has area 6. It spans columns 2 to 4 in rows 1 and 2.
Checking every possible rectangle is far too slow. But each row can be turned into the previous problem: Largest Rectangle in Histogram.
Build a histogram for each row: the height of a column is the number of consecutive 1s ending at that row. A 0 resets that column to height 0. Run the histogram stack algorithm on each row, and keep the largest area.
Row 0 gives heights 1, 0, 1, 0, 0, and the best area is 1. Row 1 gives 2, 0, 2, 1, 1, and the best is 3. Row 2 gives 3, 1, 3, 2, 2, and the histogram finds 6: height 2 across three columns. Row 3 gives 4, 0, 0, 3, 0, and the best is 4. The answer is 6.
In code, keep one heights array. For each row, add 1 to a column on a 1, or reset it to 0 on a 0. Then call the largest rectangle in histogram function, and keep the maximum. It's O of rows times columns time, and O of columns space.
Remember: a 2D rectangle problem becomes a 1D histogram per row. Reuse the monotonic stack from problem 84.