Pattern visualizer
Maximal Rectangle
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. 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..
Row-by-row histogram + monotonic stack
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.
1FUNCTION maximalRectangle(M):2 heights <- ZEROS(LENGTH(M[0]))3 best <- 04 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] + 18 ELSE:9 heights[c] <- 010 best <- MAX(best, largestRectangle(heights))11 RETURN best
← / → step · space play · Home restart