You are given a matrix of 0s and 1s. You want to find the largest rectangle containing only 1s. Which approach leverages the 'largest rectangle in histogram' problem?
-
A
Process each row as a histogram of heights, apply stack-based largest rectangle algorithm
-
B
Use DP to track 2D prefix sums then iterate over all pairs
-
C
Run BFS from every cell with value 1
-
D
Sort cells by value and use union-find