DSA Tracker

Visualize

Maximal Rectangle

Row-by-row histogram + monotonic stack

time O(rows x cols)space O(cols)

A rectangle of 1s has to stop somewhere, so pin it down by its BOTTOM edge: every rectangle in the matrix ends on exactly one row. Fix that row and the problem collapses — for each column, count how many unbroken 1s sit directly above it, and those counts are a histogram bar chart. The largest rectangle of 1s ending on this row is precisely the largest rectangle in that histogram, which the monotonic stack already solves in one pass. Building the next row's histogram is a single sweep: a 1 adds one to the column's height, a 0 severs the run and knocks it to 0. So the whole matrix costs one histogram scan per row.

Details

Animated on: matrix = [[1,0,1,1],[1,1,1,1],[0,1,1,1]] — find the area of the largest rectangle containing only 1s.

Problem:Maximal RectangleHard

Pattern:Monotonic Stack

Row-by-row histogram + monotonic stack

step 1 / 11

0
[0]
0
[1]
0
[2]
0
[3]

The matrix is 3 rows of 4 columns and every rectangle of 1s has to END on some row. So walk the rows top-down and keep one number per column: how many unbroken 1s sit directly above, counting the current row. Those 4 numbers are a histogram, and the widest block of 1s ending on this row is exactly the largest rectangle in it. Everything starts at 0 before any row is read.

Pseudocode
1FUNCTION maximalRectangle(M):
2  heights <- ZEROS(LENGTH(M[0]))
3  best <- 0
4  FOR r <- 0 TO LENGTH(M) - 1:
5    FOR c <- 0 TO LENGTH(heights) - 1:
6      IF M[r][c] = 1:
7        heights[c] <- heights[c] + 1
8      ELSE:
9        heights[c] <- 0
10    best <- MAX(best, largestRectangle(heights))
11  RETURN best

← / → step · space play · Home restart

Every step in words

Show all 11 steps
  1. The matrix is 3 rows of 4 columns and every rectangle of 1s has to END on some row. So walk the rows top-down and keep one number per column: how many unbroken 1s sit directly above, counting the current row. Those 4 numbers are a histogram, and the widest block of 1s ending on this row is exactly the largest rectangle in it. Everything starts at 0 before any row is read.
  2. Row 0 reads 1 0 1 1. Column 1 holds a 0, which severs anything built above — that column's height drops straight back to 0, not down by one. The histogram for row 0 is 1, 0, 1, 1.
  3. The tallest block that fits under 1, 0, 1, 1 covers columns 2..3 at height 1, area 2 — meaning 2 ones form a solid rectangle whose bottom edge is row 0.
  4. Row 1 reads 1 1 1 1. Every column holds a 1, so every height grows by one. The histogram for row 1 is 2, 1, 2, 2.
  5. The tallest block that fits under 2, 1, 2, 2 covers columns 2..3 at height 2, area 4 — meaning 4 ones form a solid rectangle whose bottom edge is row 1.
  6. Row 2 reads 0 1 1 1. Column 0 holds a 0, which severs anything built above — that column's height drops straight back to 0, not down by one. The histogram for row 2 is 0, 2, 3, 3.
  7. Now run the histogram scan on 0, 2, 3, 3. Pushing columns left to right keeps the stack in never-decreasing height order (0 <= 2 <= 3 <= 3), so whatever sits directly below a column on the stack is the NEAREST column to its left that is not taller — one pop hands over both edges of that column's block at once.
  8. Column 3 stands 3 tall, and there is nothing past column 3, so column 3 can never stretch further right — settle it now. Below it on the stack sits column 2, height 3, the nearest column to its left that is not taller: the block runs columns 3..3, width 1, area 3 x 1 = 3, the biggest block of 1s found anywhere so far.
  9. Column 2 stands 3 tall, and there is nothing past column 3, so column 2 can never stretch further right — settle it now. Below it on the stack sits column 1, height 2, the nearest column to its left that is not taller: the block runs columns 2..3, width 2, area 3 x 2 = 6, the biggest block of 1s found anywhere so far.
  10. Column 1 stands 2 tall, and there is nothing past column 3, so column 1 can never stretch further right — settle it now. Below it on the stack sits column 0, height 0, the nearest column to its left that is not taller: the block runs columns 1..3, width 3, area 2 x 3 = 6, which loses to the 6 already banked.
  11. Every row has served as a bottom edge, so every rectangle of 1s has been measured exactly once. The winner ends on row 2, spans columns 2..3 and stands 3 rows tall: area 6.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Maximal Rectangle in the editorAll Stack problemsBack to roadmap