Skip to main content

98. Maximal Rectangle

hardAsked at Workday

Find the largest rectangle of 1s in a binary matrix. Workday uses this as the 2D extension of Largest Rectangle in Histogram — same shape as finding the largest cohort of co-employed-in-region records across employees and timeline.

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

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2025)— Workday SDE3 onsite.

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. Try every rectangle

Iterate top-left and bottom-right corners.

Time
O((rc)^2)
Space
O(1)
// catastrophic

Tradeoff: Too slow.

2. Per-row histogram + LC 84

For each row, compute heights[j] = consecutive 1s ending at this row. Then run Largest Rectangle in Histogram on heights.

Time
O(rows * cols)
Space
O(cols)
function maximalRectangle(matrix) {
  if (!matrix || matrix.length === 0) return 0;
  const cols = matrix[0].length;
  const heights = new Array(cols).fill(0);
  let best = 0;
  function largestRect(h) {
    const stack = [];
    let maxArea = 0;
    for (let i = 0; i <= h.length; i++) {
      const cur = i === h.length ? 0 : h[i];
      while (stack.length > 0 && h[stack[stack.length - 1]] > cur) {
        const top = stack.pop();
        const width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
        maxArea = Math.max(maxArea, h[top] * width);
      }
      stack.push(i);
    }
    return maxArea;
  }
  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, largestRect(heights));
  }
  return best;
}

Tradeoff: Decomposes into r calls of LC 84 (one per row), each O(c). Total O(rc).

Workday-specific tips

Workday wants the decomposition into LC 84. Articulate this — 'I'll reduce to a 1D problem by treating each row as a histogram base'. Reuse the monotonic-stack solution.

Common mistakes

  • Recomputing heights from scratch per row instead of incrementally.
  • Treating heights as integer when matrix is strings ('0' vs '1') — type confusion.
  • Not resetting heights[j] to 0 on a '0' cell.

Follow-up questions

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

  • Maximal Square (LC 221) — only squares.
  • Largest Plus Sign (LC 764).
  • What if matrix is sparse?

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 incremental heights?

heights[j] for row i = heights[j] for row i-1 + 1 if matrix[i][j]=='1', else 0. Avoids re-scanning columns.

Why LC 84?

For each row, the histogram is the column-wise consecutive 1-count ending at that row. The largest rectangle on that histogram = largest rectangle whose bottom is this row.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →