Pattern this teaches:Monotonic Stack
Maximal Rectangle
A hard Stack interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Stack
- Sheets
- 2
- Core for
- 9 roles
The problem
Given a rows by cols binary matrix filled with 0s and 1s, find the largest rectangle containing only 1s and return its area.
Example 1
- Input
- matrix = [["1","1","0","1"],["1","1","1","1"],["0","1","1","1"],["1","0","1","1"]]
- Output
- 6
- Why
- The block of 1s covering rows 1 to 3 in columns 2 and 3 has area 6, the largest all-ones rectangle.
Example 2
- Input
- matrix = [["0"]]
- Output
- 0
- Why
- The only cell is 0, so no rectangle of 1s exists.
Example 3
- Input
- matrix = [["1"]]
- Output
- 1
- Why
- Single cell with 1 gives a rectangle of area 1.
Constraints
- rows == matrix.length
- cols == matrix[i].length
- 1 <= rows, cols <= 200
- matrix[i][j] is '0' or '1'
How to think about it
Updated 2026-09-29Every rectangle of 1s sits on some row as its bottom base. If each cell in row r knows the number of consecutive 1s standing directly above it, that row becomes a standard histogram. Scanning row by row, updating column heights incrementally, and applying the largest rectangle histogram subroutine reduces a 2D geometric search to independent 1D stack passes.
Approaches, worst first
Check all bounding boxes
time O(rows^2 * cols^2) · space O(rows * cols)
Iterate over all top-left `(r1, c1)` and bottom-right `(r2, c2)` coordinate pairs, then verify whether all cells inside the candidate rectangle equal '1' via 2D prefix sums. Evaluating O(rows^2 * cols^2) candidate submatrices is far too slow.
Row-by-row histogram with monotonic stackWrite this one
time O(rows * cols) · space O(cols)
Maintain an array `heights` of length `cols`. For each row, increment `heights[j]` if `matrix[i][j] == '1'`, or reset it to 0 if `matrix[i][j] == '0'`. Run the O(cols) monotonic stack histogram solver on `heights` after each row and track the global maximum area.
Where people lose marks · 3
- Failing to reset `heights[j] = 0` when encountering a `'0'`: a 0 breaks the vertical continuity of the column, so earlier 1s cannot support any rectangle extending through this row.
- Characters versus numbers: matrix values are characters `'0'` and `'1'`, so treating them as boolean truthy values causes `'0'` to evaluate as truthy.
- Single-column or single-row matrices: dimensions can be 1x1, which should not trigger out-of-bounds errors or sentinel mishandling.
The theory behind it
Stack — the ground this problem stands on. All Stack problems
What Stack is
A stack is a vertical pile of cafeteria trays where items enter and depart from one single opening at the top. The most recent item set down is the first one retrieved, while items deposited earlier remain buried underneath until newer arrivals are lifted away. This strict last-in, first-out sequence guarantees that older context stays preserved until all newer nested actions run to completion.
When to reach for it
Reach for a stack whenever an algorithm encounters nested structures like matched brackets, tags, or algebraic formulas. Problems demanding undo operations, function execution histories, or evaluating postfix arithmetic require this discipline. It is also the primary structure for monotonic queries where a task asks for the nearest greater or smaller value adjacent to each position in a series.
How the pattern works
Picture peeling layers back in exact reverse order of their arrival. Push items as pending jobs or unclosed delimiters encounter the scan. When closing boundaries appear, pop the topmost entry and check for compatibility. For monotonic patterns, maintain an invariant where elements on the stack remain strictly increasing or decreasing; pop any items that violate this rule before recording candidate answers and pushing the current item.
More Stack problems
Target Roles
Core requirement for 9 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .