Maximal Rectangle
Find the largest rectangle of 1s in a binary matrix by turning each row into a histogram of column heights and solving it with a monotonic stack.
Problem Understanding
Maximal Rectangle: given a rows × cols binary matrix of '0' and '1', return the area of the largest rectangle containing only 1s.
Example: the 4 × 5 matrix [[1,0,1,0,0],[1,0,1,1,1],[1,1,1,1,1],[1,0,0,1,0]] returns 6: rows 1 to 2, columns 2 to 4.
The Intuition: Every Row Is the Floor of a Histogram
Pick a row and treat it as the bottom edge of the rectangle. Looking up each column, count how many 1s are stacked unbroken above it, ending on this row. Those counts are bars of a histogram, and every all-1 rectangle sitting on this row fits under it.
- Update
heightsrow by row: add 1 for a'1', reset to 0 for a'0'. - Solve each row's histogram with Largest Rectangle in Histogram: an increasing monotonic stack that measures a bar's rectangle when a bar no taller arrives.
- The answer is the best area over all rows.
The square-only version, Maximal Square, has a simpler DP; for rectangles the histogram view is the standard approach.
Interactive Walkthrough
The grid shows the matrix; the row being solved is labelled. Under it, heights is that row's histogram. Each pop measures a rectangle (solid) and the best so far is tinted. Try Plus to see the best rectangle found as both a wide bar and a tall column.
Dry Run Table
Input: example 1.
| Row | heights | Best rectangle on this row | Best so far |
|---|---|---|---|
| 0 | [1, 0, 1, 0, 0] | 1 × 1 | 1 |
| 1 | [2, 0, 2, 1, 1] | height 1 over columns 2..4 = 3 | 3 |
| 2 | [3, 1, 3, 2, 2] | height 2 over columns 2..4 = 6 | 6 |
| 3 | [4, 0, 0, 3, 0] | height 4 in column 0 = 4 | 6 |
Answer: 6, rows 1 to 2 by columns 2 to 4.
The Solution Template
A heights array carried down the rows, and the Largest Rectangle in Histogram stack run once per row. Position n is a virtual bar of height 0 that empties the stack.
Maximal Rectangle Code
1var maximalRectangle = function(matrix) {2 if (!matrix.length) return 0;3 const n = matrix[0].length, heights = Array(n).fill(0);4 let best = 0;5 for (const row of matrix) {6 for (let j = 0; j < n; j++) heights[j] = row[j] === '1' ? heights[j] + 1 : 0;7 const stack = [-1];8 for (let i = 0; i <= n; i++) {9 const h = i < n ? heights[i] : 0;10 while (stack[stack.length - 1] !== -1 && heights[stack[stack.length - 1]] >= h) {11 const height = heights[stack.pop()];12 best = Math.max(best, height * (i - stack[stack.length - 1] - 1));13 }14 stack.push(i);15 }16 }17 return best;18};
Edge Cases & Common Mistakes
- All zeros: no rectangle; return 0.
- Forgetting to reset on 0: a column of 1s broken by a 0 must start counting again, or rectangles cross the gap.
- Not flushing the stack: without the virtual height-0 bar at
i = n, bars still on the stack at the end of a row are never measured. - Characters vs numbers: LeetCode's matrix holds
'0'and'1'characters; compare with'1', not1. - Brute force over all corners: O(rows² · cols²) or worse; the histogram view is linear in the matrix size.
Summary
Carry a heights array down the rows (add 1 on a '1', reset on a '0') and run Largest Rectangle in Histogram on each row with a monotonic stack. The best area over all rows is the answer. O(rows · cols) time, O(cols) space.
More practice: DSA interview questions with answers · patterns cheat sheet