Skip to main content

99. Maximal Rectangle

hardAsked at Reddit

Find the largest all-1s rectangle in a binary matrix. Reddit uses this to test reduction from 2D to 1D histogram — the same shape used when computing the largest contiguous active region on their heatmap of subreddit activity over time.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Reddit loops.

  • Glassdoor (2026-Q1)— Reddit data-team 2D DP hard.

Problem

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

Constraints

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

Examples

Example 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

Example 2

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

Example 3

Input
matrix = [["1"]]
Output
1

Approaches

1. Brute force all rectangles

Try every (r1, c1, r2, c2). Check if all 1s.

Time
O((rc)^2)
Space
O(1)
// Anti-pattern: too slow.

Tradeoff: TLE.

2. Row-wise histogram + LC 84 (optimal)

For each row, build a histogram of heights of consecutive 1s ending here. Solve largest rectangle in histogram for each row.

Time
O(rows * cols)
Space
O(cols)
function maximalRectangle(matrix) {
  if (!matrix.length) return 0;
  const cols = matrix[0].length;
  const heights = new Array(cols).fill(0);
  let best = 0;
  for (const row of matrix) {
    for (let j = 0; j < cols; j++) heights[j] = row[j] === '1' ? heights[j] + 1 : 0;
    best = Math.max(best, largestRectangleArea(heights));
  }
  return best;
}
function largestRectangleArea(heights) {
  const stack = [], h = [...heights, 0];
  let best = 0;
  for (let i = 0; i < h.length; i++) {
    while (stack.length && h[stack[stack.length - 1]] > h[i]) {
      const top = stack.pop();
      const width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
      best = Math.max(best, h[top] * width);
    }
    stack.push(i);
  }
  return best;
}

Tradeoff: Linear in matrix size. The reduction to LC 84 per row is the canonical approach.

Reddit-specific tips

Reddit interviewers want the LC 84 reduction. Bonus signal: walk through how heights[j] accumulates and resets at each row.

Common mistakes

  • Resetting heights to 0 on '1' (must reset on '0', accumulate on '1').
  • Calling LC 84 with wrong dimensions.
  • Off-by-one on stack-pop width.

Follow-up questions

An interviewer at Reddit may pivot to one of these next:

  • Largest rectangle of 1s (LC 221) — only squares.
  • Maximal square (LC 221) — DP version.
  • Submatrix sum problems.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why per-row histogram?

Each cell (i, j) contributes a 'height' = consecutive 1s ending at row i. The max rectangle bottomed at row i is the LC 84 answer on heights[].

Pure DP alternative?

Track for each (i, j): left-most, right-most, and height of 1s. O(rows * cols) time and space.

Practice these live with InterviewChamp.AI

Drill Maximal Rectangle and other Reddit interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →