Maximal Rectangle — Histogram per Row + Monotonic Stack

Problem Statement#

Given a rows x cols binary matrix filled with 0s and 1s, find the largest rectangle containing only 1s and return its area.

Constraints:

• rows == matrix.length, cols == matrix[i].length
• 1 <= rows, cols <= 200
• matrix[i][j] is '0' or '1'.

Input:  matrix = [["1","0","1","0","0"],
                  ["1","0","1","1","1"],
                  ["1","1","1","1","1"],
                  ["1","0","0","1","0"]]
Output: 6

Input:  matrix = [["0"]]
Output: 0

Why This Problem Matters#

LeetCode 85 Maximal Rectangle is the canonical "compose two patterns" interview problem and shows up at Amazon, Google, Meta, Apple, and Microsoft. The two patterns are: (1) computing column heights row by row in O(1) per cell, and (2) running the monotonic stack from Largest Rectangle in Histogram on each row. Together they give O(m times n).

Recruiters love this problem because solving it requires you to recognize that a 2D problem reduces to m instances of a 1D subproblem. Candidates who have not internalized LeetCode 84 will struggle here. Candidates who do see it cleanly demonstrate strong pattern composition skills, which is exactly what FAANG hires reward.

The Core Insight#

For each row r, define heights[c] as the number of consecutive 1s ending at row r in column c (including row r). If matrix[r][c] equals 1, heights[c] increments by 1; otherwise heights[c] resets to 0. Each row's heights array is a histogram.

For each histogram, the largest rectangle of 1s ending at that row is exactly Largest Rectangle in Histogram (LeetCode 84). Run the monotonic stack on each row's histogram and track the global maximum.

Total complexity: O(m times n) for building heights row by row plus O(n) for each histogram pass, summing to O(m times n).

Visual Dry Run#

Consider the example matrix:

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

Row-by-row heights:

Row 0: 1 0 1 0 0. Histogram max area equals 1. Row 1: 2 0 2 1 1. Histogram max area: bar of height 1 across indices 2..4 gives 3; bar of height 2 alone gives 2. Maximum is 3. Row 2: 3 1 3 2 2. Histogram max area: heights of 2 across indices 2..4 give 6 (the answer). Row 3: 4 0 0 3 0. Histogram max area: 4 alone is 4; 3 alone is 3. Maximum is 4.

Global maximum equals 6. Matches expected output.

The transition between rows is just a per-cell increment or reset, costing O(1) per cell.

Solution (Optimal)#

We reuse the histogram solution. I implement largestRectangleArea inline so the two-step structure is explicit.

from typing import List
 
def maximalRectangle(matrix: List[List[str]]) -> int:
    if not matrix or not matrix[0]:
        return 0
    rows, cols = len(matrix), len(matrix[0])
    heights = [0] * cols
    best = 0
 
    for r in range(rows):
        for c in range(cols):
            heights[c] = heights[c] + 1 if matrix[r][c] == '1' else 0
        best = max(best, _largest_rectangle(heights))
    return best
 
 
def _largest_rectangle(heights: List[int]) -> int:
    stack = []
    best = 0
    arr = heights + [0]
    for i, h in enumerate(arr):
        while stack and arr[stack[-1]] >= h:
            top = stack.pop()
            left = stack[-1] if stack else -1
            best = max(best, arr[top] * (i - left - 1))
        stack.append(i)
    return best

function maximalRectangle(matrix) {
  if (!matrix.length || !matrix[0].length) return 0;
  const rows = matrix.length, cols = matrix[0].length;
  const heights = new Array(cols).fill(0);
  let best = 0;
 
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      heights[c] = matrix[r][c] === '1' ? heights[c] + 1 : 0;
    }
    best = Math.max(best, largestRectangleArea(heights));
  }
  return best;
}
 
function largestRectangleArea(heights) {
  const stack = [];
  let best = 0;
  const arr = [...heights, 0];
  for (let i = 0; i < arr.length; i++) {
    while (stack.length && arr[stack[stack.length - 1]] >= arr[i]) {
      const top = stack.pop();
      const left = stack.length ? stack[stack.length - 1] : -1;
      best = Math.max(best, arr[top] * (i - left - 1));
    }
    stack.push(i);
  }
  return best;
}

Complexity. Time O(m times n) — m rows, each costing O(n) to update heights and O(n) to run the histogram stack. Space O(n) for the heights array and stack.

Common Mistakes#

• Resetting the heights array to zero between rows. You must keep the previous row's heights and only reset cells where matrix is 0.
• Forgetting to compare matrix entries as strings. LeetCode passes matrix as a 2D char array.
• Calling largestRectangleArea on the original matrix row instead of the cumulative heights. The histogram is built across rows, not within a row.
• Off-by-one in the histogram width calculation — same trap as LeetCode 84.
• Using O(m squared times n squared) brute force. It is correct but TLEs on 200 by 200 matrices.

Interview Tips#

• Open by acknowledging the brute force (try every rectangle) and computing its complexity. Then introduce the row-by-row histogram reduction.
• Walk through three rows of the example to make the heights update concrete, especially the reset-on-zero rule.
• Reference LeetCode 84 explicitly. Telling the interviewer "this reduces to Largest Rectangle in Histogram per row" is high signal.
• Discuss the alternative approach using DP on (left, right, height) per cell — slightly worse constants but same complexity.
• Mention 2D extensions: Maximum Sum Submatrix uses a similar row-compression idea with Kadane's algorithm.

Follow-up Questions#

1. What if you must return the actual rectangle coordinates, not just the area? Track the (top, bottom, left, right) when updating best.
2. What if 1s come and go (online updates)? Recomputing per row is O(n times m); use a 2D segment tree for sub-linear updates.
3. What is the largest rectangle of all the same digit (not just 1s)? Run the algorithm separately for each digit, partitioning by value.
4. What if the matrix is sparse and stored as a list of 1-coordinates? Compress rows and columns first; histogram approach still applies.
5. How would you parallelize? Each row's histogram pass is independent given the heights from the previous row, but row updates are sequential — pipeline them.

Key Takeaways#

• Maximal Rectangle reduces 2D to m instances of the 1D Largest Rectangle in Histogram problem.
• Row-by-row, increment heights[c] on '1' and reset to 0 on '0'.
• Each histogram pass uses the monotonic increasing stack, costing O(n) per row.
• Total time O(m times n), space O(n) for heights and stack.
• This is a textbook "compose two patterns" question — practice both LeetCode 84 and this together.
• Pattern recognition matters: many 2D problems reduce to 1D subproblems via per-row compression.