Tuesday, January 21, 2014

Maximal Rectangle (Java)


Maximal Rectangle

 Total Accepted: 2599 Total Submissions: 12591
Given a 2D binary matrix filled with 0's and 1's,
 find the largest rectangle containing all ones and 
return its area.

Similar question with largest rectangle in histogram but 
more tough.
we can apply a helper table to convert matrix to another
int[][] helper with calculate the current height for 1 at each 
column until current row.
Such as
char[][] matrix       -> int[][] helper
0,0,0,1,0                   0,0,0,1,0
0,1,1,0,1                   0,1,1,0,1
0,1,1,1,0                   0,2,2,1,0
0,0,1,0,1                   0,0,3, 0,1

then we can apply the method used in largest rectangle in
histogram to get max area which used current row as bottom
then keep updating max area.