Sign in to watch this lesson
Advanced - Dynamic Programming · 4:34
Largest Zero Submatrix (Stack + Row DP)
To find the largest all-zero rectangle in a grid, we fix the rectangle's bottom row and sweep it downward, keeping one number per column: the row of the nearest blocked cell above. That turns every row into a histogram, where the best rectangle is a bar's height times the gap between the nearest shorter bars on each side, and a monotonic stack finds those walls in one linear pass, for O(n·m) time and O(m) memory.
You will learn
- Maintain d[j], the row of the nearest blocked cell at or above the current row, updating only the blocked cells of each new row in O(m) memory
- Turn each row into a histogram of heights i - d[j] and compute the best rectangle for a column as height × (k2 - k1 - 1)
- Find k1 and k2 for every column with a monotonic stack (pop while d[top] <= d[j]) in amortised O(1) per column, resetting the stack between the passes
- Recognise disguised versions (all-positive windows in a sign heatmap, free space on a floor plan) and use 64-bit areas