Skip to main content

98. Maximal Rectangle

hardAsked at Snowflake

Find the largest rectangle of 1s in a binary matrix. Snowflake asks this as the 2D extension of Largest-Rectangle-in-Histogram — relevant to range-max queries over rectangular data tiles.

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

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

  • Glassdoor (2025-Q4)— Snowflake execution-engine team uses this in onsites.
  • LeetCode Discuss (2025-10)— Reported at Snowflake SDE-II screens.

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

Approaches

1. Brute force every rectangle

Try every (r1, c1, r2, c2) corner; check whether all cells are 1.

Time
O((rows * cols)^2)
Space
O(1)
// outline — too slow.

Tradeoff: Quartic-ish. Don't ship.

2. Histogram per row + LC 84 (optimal)

For each row, compute a histogram (column heights of consecutive 1s ending at this row). Apply Largest-Rectangle-in-Histogram per 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 c = 0; c < cols; c++) {
      heights[c] = row[c] === '1' ? heights[c] + 1 : 0;
    }
    best = Math.max(best, largestRectangleArea(heights));
  }
  return best;
  function largestRectangleArea(h) {
    const stack = [];
    let area = 0;
    for (let i = 0; i <= h.length; i++) {
      const cur = i === h.length ? 0 : h[i];
      while (stack.length && h[stack[stack.length - 1]] > cur) {
        const top = stack.pop();
        const left = stack.length ? stack[stack.length - 1] : -1;
        area = Math.max(area, h[top] * (i - left - 1));
      }
      stack.push(i);
    }
    return area;
  }
}

Tradeoff: Reduce 2D to 1D using row-wise histograms. The monotonic-stack inner loop is LC 84.

Snowflake-specific tips

Snowflake interviewers want the reduction: '2D maximal rectangle reduces to row-wise LC 84'. Bonus signal: connect to range-max over rectangular data tiles — Snowflake's clustered storage uses 2D layouts where range queries over column tiles use similar reductions.

Common mistakes

  • Recomputing heights from scratch each row — must increment from previous row.
  • Resetting heights[c] to 0 on '0' but forgetting to keep on '1'.
  • Inlining LC 84 unfamiliarly — practice that separately first.

Follow-up questions

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

  • Count rectangles instead of finding the max.
  • How does Snowflake range-query 2D data tiles?
  • Maximal Square (LC 221) — simpler DP.

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 histograms?

Each row's histogram encodes 'maximum height of consecutive 1s ending at this row, per column'. The largest rectangle has a bottom edge on some row, and per-row LC 84 finds the best rectangle with that bottom edge.

How does this connect to data tiles?

Snowflake's clustered storage tiles 2D — partition by date AND by user ID, for example. Range-max queries over the 2D tile structure use similar 1D-reductions.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →