Pattern visualizer

Maximum Rectangle in Binary Matrix

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. 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..

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)step 1 / 8

c0c1c2c3c4

r0r1r2r3

line 5

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

Where to practice Dynamic Programming

Practice Dynamic Programming problems All Dynamic Programming problems Back to roadmap