Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area
The idea is to scan the matrix row by row. In this row, we calculate a histogram of 1's that are directly continuously above the row. Then we could solve the maximal area of histogram using "Largest Rectangle in Histogram". Then entire algorithm takes O(n^2) time.
No comments:
Post a Comment