Skip to main content

98. Maximal Rectangle

hardAsked at Salesforce

Find the largest rectangle of 1s in a binary matrix. Salesforce uses this to test the row-by-row histogram reduction.

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

Source citations

Public interview reports confirming this problem appears in Salesforce loops.

  • Glassdoor (2026-Q1)— Salesforce uses this in their data-cube rendering for high-density displays.
  • LeetCode Discuss (2025)— Hard variant requiring composition of LC 84.

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

Example 2

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

Approaches

1. Brute force every rectangle

Try every (top-left, bottom-right) pair; check all-ones.

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

Tradeoff: TLE.

2. Row-by-row histogram

Treat each row as the base of a histogram where heights = consecutive 1s ending at that row. Run LC 84 on each row.

Time
O(m*n)
Space
O(n)
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 = [];
  let best = 0;
  for (let i = 0; i <= heights.length; i++) {
    const cur = i === heights.length ? 0 : heights[i];
    while (stack.length && cur < heights[stack[stack.length - 1]]) {
      const top = stack.pop();
      const width = stack.length ? i - stack[stack.length - 1] - 1 : i;
      best = Math.max(best, heights[top] * width);
    }
    stack.push(i);
  }
  return best;
}

Tradeoff: O(m*n) total. The composition of LC 84 over each row is Salesforce's preferred approach.

Salesforce-specific tips

Salesforce uses this in their data-cube rendering for high-density displays (finding the largest contiguous filled region). They grade on whether you recognize this as 'LC 84 applied to each row's histogram'. Bonus signal: clarify that 'heights[j] += 1' on a 1 and 'heights[j] = 0' on a 0 maintains the invariant that heights[j] is the consecutive run of 1s ending at the current row.

Common mistakes

  • Allocating a fresh heights array each row — works but O(n) extra alloc per row.
  • Forgetting to reset heights[j] to 0 on '0' — gives wrong rectangles.
  • Not extracting largestRectangleArea as a subroutine — copy-paste bugs.

Follow-up questions

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

  • Maximal Square (LC 221) — squares only.
  • Number of Submatrices that Sum to Target (LC 1074).
  • Generalize to k-colored matrices.

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 update heights in place?

Saves O(n) allocation per row. The carryover represents consecutive 1s, which is exactly the running height needed for the histogram.

What if the matrix is sparse?

The algorithm doesn't exploit sparsity. For very sparse matrices, alternative approaches (like 'find connected components') might be faster.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →