Skip to main content

96. Maximal Rectangle

hardAsked at Plaid

Find the largest all-1's rectangle in a binary matrix. Plaid asks this as a 'reduce-to-known-problem' classic — the maximal rectangle in a binary matrix reduces to multiple histogram problems.

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

Source citations

Public interview reports confirming this problem appears in Plaid loops.

  • Glassdoor (2025)— Plaid SWE III onsite — follow-up to LC 84.
  • LeetCode Discuss (2026)— Plaid 2D extension.

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 <= row, 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

Approaches

1. Try every rectangle

O(r^2 c^2) candidates × O(1) each.

Time
O(r^2 c^2)
Space
O(1)
// Way too slow.

Tradeoff: TLE.

2. Row-by-row histogram

For each row, build a 'heights' array where heights[c] is the number of consecutive 1's ending at this row in column c. Then run LC 84 on heights.

Time
O(r * c)
Space
O(c)
function maximalRectangle(matrix) {
  if (matrix.length === 0) return 0;
  const cols = matrix[0].length;
  const heights = new Array(cols).fill(0);
  let best = 0;
  for (const row of matrix) {
    for (let c = 0; c < cols; c++) {
      heights[c] = row[c] === '1' ? heights[c] + 1 : 0;
    }
    best = Math.max(best, largestRectangleArea(heights));
  }
  return best;
}
function largestRectangleArea(heights) {
  // same as LC 84
  const stack = [];
  let best = 0;
  const h = [...heights, 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: Reduction to LC 84. Total O(r * c) — each row updates heights in O(c) and runs histogram in O(c).

Plaid-specific tips

Plaid grades this on whether you spot the reduction to LC 84. Bonus signal: state out loud 'for each row, the problem reduces to histogram max-rectangle.' Connect to time-windowed metrics where each row is a time bucket and columns are merchants.

Common mistakes

  • Reset heights on a zero, but forgetting that — accumulates incorrectly.
  • Re-running histogram on heights for every cell instead of every row.
  • Off-by-one in the heights update.

Follow-up questions

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

  • Maximal square (LC 221) — square instead of rectangle, simpler DP.
  • Largest rectangle containing at most k zeros.
  • Maximal rectangle in a non-rectangular shape.

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 does the reduction work?

Any all-1's rectangle has a bottom edge. Pinning that bottom edge to row r, the rectangle's column-wise heights form a histogram. The largest histogram rectangle is the largest such rectangle ending at row r.

Why iterate per row?

Each row gives O(c) extra work to update heights, and O(c) for histogram. Total O(r*c) — same as a single scan.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →