DSA Tracker

Visualize

Maximal Rectangle (Dynamic Programming)

width[r][c] = run of 1s ending here, then scan upward shrinking the min width

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

Turn every row into a running count: width[r][c] is how many 1s in a row end at column c, reset to 0 the moment a 0 appears. That single pass is dynamic programming on rows — each cell only needs the cell to its left. A rectangle of 1s ending at (r, c) is then just a matter of asking how far up it can stretch: walk upward from row r, and at each row take the minimum width seen so far, because a rectangle can only be as wide as its narrowest row. Multiply that shrinking width by the height climbed and the largest value found anywhere is the answer.

Details

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

Problem:Maximal Rectangle (Dynamic Programming)Hard

width[r][c] = run of 1s ending here, then scan upward shrinking the min width

step 1 / 8

Row 0 of the matrix is "10100" — reading left to right, a '1' extends the run from the cell to its left and a '0' resets it. width[0] = [1, 0, 1, 0, 0].

Pseudocode
1FUNCTION maxRectangle(M):
2  width <- ZEROS(ROWS(M), COLS(M))
3  FOR r FROM 0 TO ROWS(M) - 1:
4    FOR c FROM 0 TO COLS(M) - 1:
5      width[r][c] <- IF M[r][c] = 1 THEN width[r][c-1] + 1 ELSE 0
6  best <- 0
7  FOR r FROM 0 TO ROWS(M) - 1:
8    FOR c FROM 0 TO COLS(M) - 1:
9      minWidth <- width[r][c]
10      FOR k FROM r DOWNTO 0:
11        minWidth <- MIN(minWidth, width[k][c])
12        IF minWidth = 0: BREAK
13        best <- MAX(best, minWidth * (r - k + 1))
14  RETURN best

← / → step · space play · Home restart

Every step in words

Show all 8 steps
  1. Row 0 of the matrix is "10100" — reading left to right, a '1' extends the run from the cell to its left and a '0' resets it. width[0] = [1, 0, 1, 0, 0].
  2. Row 1 of the matrix is "10111" — reading left to right, a '1' extends the run from the cell to its left and a '0' resets it. width[1] = [1, 0, 1, 2, 3].
  3. Row 2 of the matrix is "11111" — reading left to right, a '1' extends the run from the cell to its left and a '0' resets it. width[2] = [1, 2, 3, 4, 5].
  4. Row 3 of the matrix is "10010" — reading left to right, a '1' extends the run from the cell to its left and a '0' resets it. width[3] = [1, 0, 0, 1, 0].
  5. Scanning upward from the winning cell (2, 4): width[2][4] = 5 on its own already gives a candidate area of 5.
  6. Row 1 narrows it: width[1][4] = 3 shrinks the min width to 3. A 2-row-tall rectangle of width 3 has area 6 — the new best.
  7. One row further up, width[0][4] = 0 — row 0 has no run at all in this column, so the rectangle cannot grow taller and the scan stops here. Best area found stays at 6.
  8. Every cell tried, and nothing beat it: the largest rectangle of 1s has area 6, spanning rows 1-2 and columns 2-4 (2 x 3).

Now solve it yourself

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

Solve Maximal Rectangle (Dynamic Programming) in the editorAll Dynamic Programming problemsBack to roadmap