Maximal Rectangle (Java)

LeetCode

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.