Stack crash course ↗ · 32

85. Maximal Rectangle

Find the largest rectangle of 1s in a binary matrix. The trick is to treat each row as the floor of a histogram of consecutive 1s above it, then run Largest Rectangle in Histogram (a monotonic stack) once per row — turning a 2D search into a stack of 1D ones in O(rows × cols).

● HardMonotonic StackHistogramTypeScript

PROBLEM What we're solving

Given a binary matrix of '0' / '1' characters, return the area of the largest rectangle containing only 1s.

Example:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

The biggest all-1s rectangle spans rows 1–2, columns 2–4 (a 2×3 block of 1s), giving area 2 × 3 = 6. Answer: 6.

The hard part: a valid rectangle must be solid 1s across multiple rows and columns at once. Brute-forcing every (top, bottom, left, right) is far too slow — we need structure.

KEY IDEA Every row is a histogram; reuse Largest Rectangle in Histogram

Insight → Sweep top to bottom. For the current row, let heights[j] be the number of consecutive 1s in column j ending at this row. That array is a histogram, and the largest all-1s rectangle whose bottom edge sits on this row is exactly the Largest Rectangle in Histogram(LC 84) of those heights. Run LC 84's monotonic-increasing stack once per row and keep the global max.

Because every all-1s rectangle has some bottom row, considering each row as the floor catches all of them. We never have to think in 2D again — each row collapses to a single 1D histogram problem we already know how to solve in O(cols).

RECIPE Build the running histogram, then call LC 84 per row

  • 0 · Init. heights = new Array(cols).fill(0) and maxArea = 0. heights persists across rows — it carries the running column streaks.
  • 1 · Update heights. For each column j in the current row: if the cell is '1', do heights[j] += 1 (the streak grows); if it is '0', set heights[j] = 0 (the column is broken).
  • 2 · Largest Rectangle in Histogram. Call largestRectangleArea(heights) — the LC 84 monotonic increasing stack of [startIndex, height] pairs, popping and computing h × width whenever a shorter bar arrives, with a sentinel 0 to flush.
  • 3 · Track the max. maxArea = Math.max(maxArea, …) after each row.
  • 4 · Return. After the last row, return maxArea.
Classic confusion → on a '0' cell you must RESET heights[j] = 0, not leave it or decrement it. A 0 severs the column: no all-1s rectangle can pass through that gap, so the streak above it is useless for any rectangle with this row as the floor. Forgetting the reset (e.g. doing heights[j] -= 1) silently counts rectangles that contain a 0.

COST Complexity & alternatives

Brute force (all corners)
O((mn)²)
Try every pair of corners and verify the block is all 1s. Hopeless for large grids.
Histogram + monotonic stack
O(mn)
Each of m rows builds heights in O(n) and runs LC 84 in O(n). O(n) stack space.

Why O(mn)?

Per row: O(n) to update heights, plus O(n) for the histogram (each bar pushed and popped at most once). Over m rows that is O(mn) total, with O(n) auxiliary space for the heights array and the stack.

Pattern transfer → this is Largest Rectangle in Histogram (LC 84) applied row by row — the exact same [startIndex, height] stack. The sibling Maximal Square (LC 221) uses the same row-sweep framing but with a DP recurrence (min of three neighbors) instead of a stack, because squares are simpler than rectangles. The running-histogram trick also powers count submatrices with all ones variants.

RUN IT Each row is a histogram — run Largest Rectangle in Histogram per row

step 0 / 29
STARTSweep top to bottom. heights[j] tracks consecutive 1s in column j ending at the current row, all starting at 0.
1function maximalRectangle(matrix: string[][]): number {
2  if (matrix.length === 0 || matrix[0].length === 0) return 0;
3  const cols = matrix[0].length;
4 
5▶  // heights[j] = run of consecutive '1's in column j, ending at the current row.
6▶  const heights: number[] = new Array(cols).fill(0);
7▶  let maxArea = 0;
8 
9  for (const row of matrix) {
10    // 1) Update the histogram for this row.
11    for (let j = 0; j < cols; j++) {
12      heights[j] = row[j] === '1' ? heights[j] + 1 : 0; // '0' resets the run
13    }
14    // 2) Largest Rectangle in Histogram on the current heights (LC 84).
15    maxArea = Math.max(maxArea, largestRectangleArea(heights));
16  }
17 
18  return maxArea;
19}
20 
21// Monotonic increasing stack of [startIndex, height] pairs — exactly LC 84.
22function largestRectangleArea(heights: number[]): number {
23  const stack: [number, number][] = [];
24  let maxArea = 0;
25 
26  for (let i = 0; i <= heights.length; i++) {
27    const curH = i < heights.length ? heights[i] : 0; // sentinel 0 flushes all
28    let start = i;
29    while (stack.length > 0 && stack[stack.length - 1][1] >= curH) {
30      const [idx, h] = stack.pop()!;
31      maxArea = Math.max(maxArea, h * (i - idx)); // width = i - idx
32      start = idx; // inherit the popped bar's left boundary
33    }
34    stack.push([start, curH]);
35  }
36 
37  return maxArea;
38}
1
0
1
0
0
1
0
1
1
1
1
1
1
1
1
1
0
0
1
0
State
row: —
heights:
00000
stack [start,h]: ∅
maxArea: 0
current rowcolumn streak feeding heightsrectangle being measuredbest rectangle so far
slowfast

TYPESCRIPT The solution, annotated

maximalRectangle.ts
function maximalRectangle(matrix: string[][]): number {
  if (matrix.length === 0 || matrix[0].length === 0) return 0;
  const cols = matrix[0].length;

  // heights[j] = run of consecutive '1's in column j, ending at the current row.
  const heights: number[] = new Array(cols).fill(0);
  let maxArea = 0;

  for (const row of matrix) {
    // 1) Update the histogram for this row.
    for (let j = 0; j < cols; j++) {
      heights[j] = row[j] === '1' ? heights[j] + 1 : 0; // '0' resets the run
    }
    // 2) Largest Rectangle in Histogram on the current heights (LC 84).
    maxArea = Math.max(maxArea, largestRectangleArea(heights));
  }

  return maxArea;
}

// Monotonic increasing stack of [startIndex, height] pairs — exactly LC 84.
function largestRectangleArea(heights: number[]): number {
  const stack: [number, number][] = [];
  let maxArea = 0;

  for (let i = 0; i <= heights.length; i++) {
    const curH = i < heights.length ? heights[i] : 0; // sentinel 0 flushes all
    let start = i;
    while (stack.length > 0 && stack[stack.length - 1][1] >= curH) {
      const [idx, h] = stack.pop()!;
      maxArea = Math.max(maxArea, h * (i - idx)); // width = i - idx
      start = idx; // inherit the popped bar's left boundary
    }
    stack.push([start, curH]);
  }

  return maxArea;
}

Reading it block by block

Lines 2–8 — setup. Guard against an empty matrix, then create heights (one slot per column, all 0) and maxArea = 0. heights lives outside the row loop so it accumulates column streaks as we descend.
Lines 11–13 — grow or reset. For each column in the current row: a '1' extends the column's run (heights[j] + 1), a '0' resets it to 0. After this loop, heights is the histogram whose floor is the current row.
Line 15 — reduce to LC 84. The largest all-1s rectangle bottomed on this row equals the largest rectangle in the heights histogram. We call largestRectangleArea and fold its result into maxArea.
Lines 22–38 — the histogram solver. A monotonic increasing stack of [startIndex, height]. When a shorter bar arrives we pop taller bars, compute h × (i − idx), and let the current bar inherit the popped bar's left boundary. A sentinel height-0 at index n flushes everything.
Line 18 — answer. After every row has played the histogram game, maxArea holds the area of the largest rectangle of 1s in the whole matrix.
Complexity → Each row costs O(n) to update heights and O(n) for the histogram stack (each bar pushed and popped at most once), so the total is O(m·n) time. Space is O(n) for the heights array plus the stack.

INTERVIEWFollow-ups they'll ask

  • "Why does treating each row as a histogram find every rectangle?" Every all-1s rectangle has a unique bottom row. When that row is the floor, the rectangle appears as a sub-rectangle of the histogram, so LC 84 on that row catches it.
  • "What is the running time, and where does it come from?" O(m·n): m rows, each O(n) to build heights plus O(n) for the monotonic stack.
  • "How would you also return the rectangle's coordinates?" In LC 84, when you update the max, record the row, the left boundary, the width, and the height; the top row is bottomRow − height + 1.
  • "What changes for Maximal Square (LC 221)?" You want the largest all-1s square, so a simpler DP works: dp[i][j] = 1 + min(up, left, up-left) on each 1 cell, tracking the max side. No stack needed.
  • "What if the input were integers, not chars?" Just compare against 1 instead of '1'; the algorithm is unchanged.

OPTIMAL Monotonic Stack

maximalRectangle.ts
function maximalRectangle(matrix: string[][]): number {
  if (matrix.length === 0 || matrix[0].length === 0) return 0;
  const cols = matrix[0].length;

  // heights[j] = run of consecutive '1's in column j, ending at the current row.
  const heights: number[] = new Array(cols).fill(0);
  let maxArea = 0;

  for (const row of matrix) {
    // 1) Update the histogram for this row.
    for (let j = 0; j < cols; j++) {
      heights[j] = row[j] === '1' ? heights[j] + 1 : 0; // '0' resets the run
    }
    // 2) Largest Rectangle in Histogram on the current heights (LC 84).
    maxArea = Math.max(maxArea, largestRectangleArea(heights));
  }

  return maxArea;
}

// Monotonic increasing stack of [startIndex, height] pairs — exactly LC 84.
function largestRectangleArea(heights: number[]): number {
  const stack: [number, number][] = [];
  let maxArea = 0;

  for (let i = 0; i <= heights.length; i++) {
    const curH = i < heights.length ? heights[i] : 0; // sentinel 0 flushes all
    let start = i;
    while (stack.length > 0 && stack[stack.length - 1][1] >= curH) {
      const [idx, h] = stack.pop()!;
      maxArea = Math.max(maxArea, h * (i - idx)); // width = i - idx
      start = idx; // inherit the popped bar's left boundary
    }
    stack.push([start, curH]);
  }

  return maxArea;
}
Complexity → Each row costs O(n) to update heights and O(n) for the histogram stack (each bar pushed and popped at most once), so the total is O(m·n) time. Space is O(n) for the heights array plus the stack.

ALT 1 DP — height / left / right boundary arrays per row

O(m·n) time · O(n) space

Same row-sweep, but instead of a stack track three rolling arrays per column — height, the leftmost and rightmost columns the all-1s span can reach — and read off height × (right − left) directly.

approach-2.ts
function maximalRectangle(matrix: string[][]): number {
  if (matrix.length === 0 || matrix[0].length === 0) return 0;
  const cols = matrix[0].length;

  // For each column, rolling across rows:
  //   height[j] = consecutive 1s in column j ending at this row
  //   left[j]   = leftmost column index of the all-1s span at height[j]
  //   right[j]  = one past the rightmost column index of that span
  const height: number[] = new Array(cols).fill(0);
  const left: number[] = new Array(cols).fill(0);
  const right: number[] = new Array(cols).fill(cols);
  let maxArea = 0;

  for (const row of matrix) {
    // 1) Heights: grow on '1', reset on '0'.
    for (let j = 0; j < cols; j++) {
      height[j] = row[j] === '1' ? height[j] + 1 : 0;
    }

    // 2) Left boundaries: sweep L→R. curLeft is the first column after the
    //    most recent '0' on THIS row. For a '1' cell the span cannot start
    //    left of curLeft, but it also inherits the tighter bound from above.
    let curLeft = 0;
    for (let j = 0; j < cols; j++) {
      if (row[j] === '1') {
        left[j] = Math.max(left[j], curLeft);
      } else {
        left[j] = 0; // boundary irrelevant; reset for next time
        curLeft = j + 1; // span for any later '1' starts after this '0'
      }
    }

    // 3) Right boundaries: sweep R→L. curRight is one past the column before
    //    the most recent '0'. Again take the tighter (smaller) bound.
    let curRight = cols;
    for (let j = cols - 1; j >= 0; j--) {
      if (row[j] === '1') {
        right[j] = Math.min(right[j], curRight);
      } else {
        right[j] = cols; // reset
        curRight = j; // span for any earlier '1' ends at this '0'
      }
    }

    // 4) Area for the rectangle floored on this row, anchored at column j.
    for (let j = 0; j < cols; j++) {
      maxArea = Math.max(maxArea, height[j] * (right[j] - left[j]));
    }
  }

  return maxArea;
}
Note → Subtle but worth memorizing: left takes a max and right takes a min so each column inherits the narrower span from the rows above — that intersection is what guarantees the whole rectangle is solid 1s. Same O(m·n) as the stack version with no explicit stack; just three linear passes per row.

ALT 2 Brute force — expand the largest all-1s rectangle from each cell

O(m·n·min(m,n)) time · O(1) space

Treat every '1' cell as a top-left corner and grow downward, shrinking the usable width as each new row introduces a '0'.

approach-3.ts
function maximalRectangle(matrix: string[][]): number {
  if (matrix.length === 0 || matrix[0].length === 0) return 0;
  const rows = matrix.length;
  const cols = matrix[0].length;
  let maxArea = 0;

  // Each cell is a candidate top-left corner.
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (matrix[r][c] !== '1') continue;

      // width = widest run of 1s we can still keep as we extend downward.
      let width = cols - c;
      for (let r2 = r; r2 < rows; r2++) {
        // Shrink width to the run of 1s in this row starting at column c.
        let runWidth = 0;
        while (runWidth < width && matrix[r2][c + runWidth] === '1') {
          runWidth++;
        }
        width = Math.min(width, runWidth);
        if (width === 0) break; // a '0' at column c (or earlier) ends the block

        const height = r2 - r + 1;
        maxArea = Math.max(maxArea, height * width);
      }
    }
  }

  return maxArea;
}
Note → For each of the m·n starting cells we extend down up to m rows, scanning up to n columns of width — worst case O(m·n·min(m,n)) and quadratic in the grid area. Clear and easy to reason about, but only viable on tiny grids; reach for the histogram or boundary-DP solution otherwise.

MNEMONIC The one-liner

"Each row is the floor of a histogram — grow the columns, reset on a 0, and ask Largest Rectangle in Histogram for the answer."

TRIGGERS When you see ___ → reach for ___

"largest rectangle of 1s in a binary matrix"row-by-row histogram + LC 84
running streak of 1s per columnheights[j] += 1, reset to 0 on a 0
largest rectangle in a histogrammonotonic increasing stack [start, height]
"largest SQUARE of 1s"DP min(up,left,upLeft)+1 (Maximal Square, LC 221)

SKELETON The reusable shape

skeleton.ts
const heights = new Array(cols).fill(0);
let maxArea = 0;
for (const row of matrix) {
  for (let j = 0; j < cols; j++)
    heights[j] = row[j] === '1' ? heights[j] + 1 : 0; // reset on '0'
  maxArea = Math.max(maxArea, largestRectangleArea(heights)); // LC 84
}
return maxArea;

FLASHCARDS Tap to flip

What does heights[j] mean, and why does it persist across rows?
The number of consecutive 1s in column j ending at the current row. It persists outside the row loop so each new row either extends the streak (+1) or resets it (0).
tap to flip
1 / 7
Answer to reveal explanations. No penalty for retries.Score: 0 / 9
QUESTION 01
What is heights[j] after processing a row?
QUESTION 02
When the current cell is '0', what do you do to heights[j]?
QUESTION 03
Which known problem do we call once per row?
QUESTION 04
For the classic matrix [[1,0,1,0,0],[1,0,1,1,1],[1,1,1,1,1],[1,0,0,1,0]], what is the answer?
QUESTION 05
What is the overall time complexity for an m × n matrix?
QUESTION 06
Why does the histogram stack maintain strictly increasing heights?
QUESTION 07
How would you adapt this to find the largest all-1s SQUARE instead?
QUESTION 08
#85 · Maximal RectangleFind the largest rectangle of 1s in a binary matrix by treating each row as a histogram of consecutive 1s above it, then running Largest Rectangle in Histogram (a monotonic stack) once per row, for O(rows × cols).Which algorithmic approach does this primarily use?
QUESTION 09
#85 · Maximal RectangleFind the largest rectangle of 1s in a binary matrix by treating each row as a histogram of consecutive 1s above it, then running Largest Rectangle in Histogram (a monotonic stack) once per row, for O(rows × cols).Which implementation correctly solves it?