[Leetcode Solution] Maximal Rectangle

Analysis

• Take advantage of this problem about how to solve the 1-dimensional problem
• Now let's take a look at how to transform this problem to the 1-dimensional one, and then use O(n) algorithm to solve it (n is the number of nodes in the rectangle)



• For each column in the matrix, we can treat it as a max rectangle in histogram problem
• Let say the second column in the matrix above, we can do such a transformation: each integer in the histogram is the number of consecutive '1' started from each element in this column, then it is 
• 0
• 3
• 0
• 4
• 2
• 4
• Then the whole 2D matrix can be transformed into several 1D problems. And this procedure can be done in O(n) taking advantage of that we can know the number of consecutive '1' in one place instantly if we know the number of consecutive '1' in the adjacent right place
• After the transformation in O(n), we will execute the max rectangle in histogram algorithm several times which equals to the number of columns. Then return the max one.

Note

Code