Skip to main content

26. Maximal Rectangle

hardAsked at Adobe

Find the largest rectangle containing only 1s in a binary matrix. Adobe uses this as a synthesis problem that combines 2D array traversal with the histogram stack algorithm — directly applicable to bounding-box detection in image segmentation and selection-region optimization in Photoshop.

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

Source citations

Public interview reports confirming this problem appears in Adobe loops.

  • Glassdoor (2026-01)— Adobe senior SDE candidates report this as a challenging synthesis problem in design-round interviews.
  • LeetCode Discuss (2025-11)— Adobe image-team interviewers cite maximal rectangle as a domain-specific hard problem.

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

Explanation: The largest rectangle has area 6 (3 columns x 2 rows in columns 2-4, rows 1-2).

Example 2

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

Approaches

1. Brute force — try all rectangles

For every pair of top-left and bottom-right corners, check if the sub-matrix contains only 1s and compute its area.

Time
O(rows^2 * cols^2)
Space
O(1)
// O(r^2 * c^2) — too slow; shown for completeness
function maximalRectangle(matrix) {
  let max = 0;
  const r = matrix.length, c = matrix[0].length;
  for (let r1 = 0; r1 < r; r1++)
    for (let c1 = 0; c1 < c; c1++)
      for (let r2 = r1; r2 < r; r2++)
        for (let c2 = c1; c2 < c; c2++) {
          let valid = true;
          for (let i = r1; i <= r2 && valid; i++)
            for (let j = c1; j <= c2 && valid; j++)
              if (matrix[i][j] === '0') valid = false;
          if (valid) max = Math.max(max, (r2-r1+1)*(c2-c1+1));
        }
  return max;
}

Tradeoff: Way too slow for 200x200 input; shown only to motivate the histogram approach.

2. Row-by-row histogram + largest rectangle in histogram

Build a heights[] array where heights[j] = number of consecutive 1s ending at the current row in column j (reset to 0 on a '0'). After each row, apply the O(n) monotonic stack largest-rectangle-in-histogram algorithm to heights[]. Take the maximum across all rows.

Time
O(rows * cols)
Space
O(cols)
function maximalRectangle(matrix) {
  if (!matrix.length) return 0;
  const cols = matrix[0].length;
  const heights = 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;
    }
    // Largest rectangle in histogram
    const stack = [];
    const h = [...heights, 0];
    for (let i = 0; i <= cols; i++) {
      while (stack.length && h[stack[stack.length-1]] > h[i]) {
        const height = h[stack.pop()];
        const width = stack.length === 0 ? i : i - stack[stack.length-1] - 1;
        maxArea = Math.max(maxArea, height * width);
      }
      stack.push(i);
    }
  }
  return maxArea;
}

Tradeoff: O(rows * cols) time, O(cols) space. The key insight is that each row defines a new histogram problem. Adobe interviewers reward candidates who recognize and reuse the histogram solution rather than treating this as a new problem.

Adobe-specific tips

Adobe interviewers consider this a synthesis test: can you recognize that updating heights row-by-row reduces the 2D problem to repeated 1D histogram problems? Drawing the heights array after each row on the whiteboard demonstrates methodical thinking. Be ready to explain why resetting heights[j]=0 on '0' is correct — a '0' breaks any upward bar, so the histogram column resets.

Common mistakes

  • Forgetting to reset heights[j] = 0 when matrix[i][j] = '0' — this overstates bar heights.
  • Rewriting the histogram subroutine from scratch without inlining or calling a helper — leads to bugs; modularize.
  • Applying the histogram algorithm without the sentinel 0 — bars remaining in the stack at row end are missed.

Follow-up questions

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

  • How does this change if '1' cells can wrap around (toroidal matrix)?
  • Can you find the top-left and bottom-right coordinates of the maximal rectangle, not just its area?
  • Largest Rectangle of 0s in a binary matrix?

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 histogram approach work for 2D?

Any maximal all-1s rectangle in the matrix must have a bottom row. For that bottom row, the rectangle's column span is constrained by the height of consecutive 1s in each column — which is exactly the histogram for that row. The largest such rectangle across all possible bottom rows is the answer.

Is there a DP approach that avoids calling the histogram algorithm?

Yes — maintain left[], right[], height[] arrays per column. For each row, update the left/right boundaries of consecutive 1s, then compute height[j] * (right[j] - left[j]) for each column. Same O(rows*cols) time and O(cols) space, but more complex to implement correctly.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →