Question

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 6.

Quick Hints

• Use memoization to calculate
• We need to find the left boundary start, right boundary start and height.
• Use three single dimension array to keep track of the above

Solution

• This problem is very similar to 221. Maximal Square
• We iterate through all rows.
• For every row we track the left boundary, right boundary and height

left(i,j) = max(left(i-1,j), cur_left), cur_left can be determined from the current row

right(i,j) = min(right(i-1,j), cur_right), cur_right can be determined from the current row

height(i,j) = height(i-1,j) + 1, if matrix[i][j]=='1' else height(i,j) = 0

Time complexity

O (m * n)

Space complexity

O (3n) for memoization

Notes