Maximal Rectangle
Row-wise histogram with monotonic stack
Row-by-row histogram heights, then apply #84 per row.
Problem
Given a binary matrix of characters '0' and '1', return the area of the largest rectangle containing only '1's.
Rows and columns are both up to 200, and the matrix can be fully zero.
Intuition
The key move is reducing the 2D problem to a sequence of 1D problems we already know how to solve.
Process rows top-to-bottom. For each row r, compute a heights array: heights[c] is the number of consecutive '1's ending at row r in column c. A '0' in the current row resets the corresponding height to 0; otherwise it increments.
Each row's heights describes a histogram, and the largest rectangle of '1's whose bottom edge sits on row r is exactly the largest rectangle in that histogram — problem #84. Taking the max across all rows gives the answer.
Approach
Brute Force
O(n² · m²)O(1)For every pair of rows (r1, r2) and every pair of columns (c1, c2), check whether the whole sub-rectangle is '1'. If so, its area is (r2 - r1 + 1) * (c2 - c1 + 1).
Four nested loops over corners plus an inner scan gives O(n² m² · max(n, m)) in the worst case. Tighter bookkeeping gets it to O(n² m²), but that's still far too slow for 200 × 200.
impl Solution {
pub fn maximal_rectangle(matrix: Vec<Vec<char>>) -> i32 {
let n = matrix.len();
if n == 0 {
return 0;
}
let m = matrix[0].len();
let mut best = 0;
for r1 in 0..n {
for c1 in 0..m {
if matrix[r1][c1] != '1' {
continue;
}
for r2 in r1..n {
if matrix[r2][c1] != '1' {
break;
}
for c2 in c1..m {
let mut all_ones = true;
'check: for r in r1..=r2 {
for c in c1..=c2 {
if matrix[r][c] != '1' {
all_ones = false;
break 'check;
}
}
}
if !all_ones {
break;
}
let area = ((r2 - r1 + 1) * (c2 - c1 + 1)) as i32;
if area > best {
best = area;
}
}
}
}
}
best
}
}
function maximalRectangle(matrix: string[][]): number {
const n = matrix.length;
if (n === 0) return 0;
const m = matrix[0].length;
let best = 0;
for (let r1 = 0; r1 < n; r1++) {
for (let c1 = 0; c1 < m; c1++) {
if (matrix[r1][c1] !== '1') continue;
for (let r2 = r1; r2 < n; r2++) {
if (matrix[r2][c1] !== '1') break;
for (let c2 = c1; c2 < m; c2++) {
let allOnes = true;
outer: for (let r = r1; r <= r2; r++) {
for (let c = c1; c <= c2; c++) {
if (matrix[r][c] !== '1') {
allOnes = false;
break outer;
}
}
}
if (!allOnes) break;
const area = (r2 - r1 + 1) * (c2 - c1 + 1);
if (area > best) best = area;
}
}
}
}
return best;
}Row Reduction + Brute Histogram
O(n · m²)O(m)Maintain a heights[c] array. After each row r:
heights[c] = matrix[r][c] == '1' ? heights[c] + 1 : 0.
For the current row, solve #84 with the brute-expand method: for every column c, expand left and right while heights[_] >= heights[c] and score heights[c] * width.
The row update is O(m); the per-row histogram scan is O(m²). Total O(n · m²). At 200 × 200 that's ~8M operations — passes, but we can do better.
impl Solution {
pub fn maximal_rectangle(matrix: Vec<Vec<char>>) -> i32 {
let n = matrix.len();
if n == 0 {
return 0;
}
let m = matrix[0].len();
let mut heights = vec![0i32; m];
let mut best = 0;
for r in 0..n {
for c in 0..m {
heights[c] = if matrix[r][c] == '1' {
heights[c] + 1
} else {
0
};
}
for c in 0..m {
let h = heights[c];
if h == 0 {
continue;
}
let mut l = c;
while l > 0 && heights[l - 1] >= h {
l -= 1;
}
let mut rr = c;
while rr + 1 < m && heights[rr + 1] >= h {
rr += 1;
}
let area = h * ((rr - l + 1) as i32);
if area > best {
best = area;
}
}
}
best
}
}
function maximalRectangle(matrix: string[][]): number {
const n = matrix.length;
if (n === 0) return 0;
const m = matrix[0].length;
const heights = new Array<number>(m).fill(0);
let best = 0;
for (let r = 0; r < n; r++) {
for (let c= 0; c < m; c++) {
heights[c]= matrix[r][c]= '1' ? heights[c] + 1 : 0;
}
for (let c= 0; c < m; c++) {
const h= heights[c];
if (h= 0) continue;
let l= c;
while (l > 0 && heights[l - 1] >= h) l--;
let rr = c;
while (rr + 1 < m && heights[rr + 1] >= h) rr++;
const area = h * (rr - l + 1);
if (area > best) best = area;
}
}
return best;
}
Row Reduction + Monotonic Stack
O(n · m)O(m)Same row-reduction — the inner histogram solve is #84's O(m) monotonic-stack pass with a sentinel at column m.
For every row we get the largest rectangle whose bottom sits on that row in linear time. Across n rows the total work is O(n · m) with O(m) extra space for heights and the stack.
impl Solution {
pub fn maximal_rectangle(matrix: Vec<Vec<char>>) -> i32 {
let n = matrix.len();
if n == 0 {
return 0;
}
let m = matrix[0].len();
let mut heights = vec![0i32; m];
let mut stack: Vec<usize> = Vec::with_capacity(m + 1);
let mut best: i32 = 0;
for r in 0..n {
for c in 0..m {
heights[c] = if matrix[r][c] == '1' {
heights[c] + 1
} else {
0
};
}
stack.clear();
for i in 0..=m {
let cur = if i == m { 0 } else { heights[i] };
while let Some(&top) = stack.last() {
if heights[top] > cur {
stack.pop();
let h = heights[top];
let width = match stack.last() {
Some(&left) => (i - left - 1) as i32,
None => i as i32,
};
let area = h * width;
if area > best {
best = area;
}
} else {
break;
}
}
stack.push(i);
}
}
best
}
}
function maximalRectangle(matrix: string[][]): number {
const n = matrix.length;
if (n === 0) return 0;
const m = matrix[0].length;
const heights = new Array<number>(m).fill(0);
const stack: number[] = [];
let best = 0;
for (let r = 0; r < n; r++) {
for (let c= 0; c < m; c++) {
heights[c]= matrix[r][c]= '1' ? heights[c] + 1 : 0;
}
stack.length= 0;
for (let i= 0; i <= m; i++) {
const cur= i= m ? 0 : heights[i];
while (stack.length > 0 && heights[stack[stack.length - 1]] > cur) {
const top = stack.pop()!;
const h = heights[top];
const width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
const area = h * width;
if (area > best) best = area;
}
stack.push(i);
}
}
return best;
}
Language notes:
- Heights reset on zero — a
'0'in the current row breaks any rectangle anchored at this column, so the height goes back to 0. No decrements; just reset. - Fresh stack per row — each row is an independent histogram problem. Reuse the allocation, not the contents.
i == msentinel — same trick as #84: treat the column past the right edge as height 0 so anything still on the stack pops.
Trace
Row-by-row heights for the example matrix, with the per-row histogram max:
| row | heights | best row rectangle |
|---|---|---|
| 0 | [1, 0, 1, 0, 0] | 1 |
| 1 | [2, 0, 2, 1, 1] | 3 |
| 2 | [3, 1, 3, 2, 2] | 6 |
| 3 | [4, 0, 0, 3, 0] | 4 |
Row 2's histogram [3, 1, 3, 2, 2] gives the 2×3 rectangle (height 2 across columns 2..4) — area 6, our global best.
Edge cases
- All-zero matrix — heights stay at 0 every row; stack pops nothing; answer is 0.
- All-one matrix — heights grow linearly; the last row's rectangle is
n × m. - Single row — the row itself is the histogram; answer equals the longest run of
'1's. - Single column — heights collapse to a scalar; answer equals the longest vertical run of
'1's. - Mixed with isolated
'1's — tiny heights constantly reset, each giving area 1 until two adjacent columns accumulate.
When a 2D grid problem asks for "largest axis-aligned rectangle with property P," try reducing each row (or column) to a histogram where the bar height equals the longest streak of P ending at that cell. If the histogram form has a known O(width) solution, the whole grid becomes O(n · m).
Takeaway
Row reduction plus #84's monotonic stack is the canonical 2D-to-1D move. It unlocks O(n · m) for the largest-ones-rectangle problem and generalizes to every "bar-height on a rolling streak" variant — largest square (#221, specialized DP), count submatrices with all ones, and so on.
In production, the same pattern shows up whenever you need the largest contiguous rectangular region in a binary mask — quick image masks, heatmap hotspots, and certain order-book depth visualizations.
More in Monotonic Stack & Deque
The basic pattern. Process right to left, stack holds candidates.
Circular array — iterate twice through the array.
Monotonic deque. Maintain decreasing order; front is always the max.
THE canonical mono stack problem. Must solve in under 15 minutes.