LeetCode: Maximal Rectangle

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

---

Intuitively, we can solve this problem by brute force. But it will be very slow. Here we can get some thinkings from the previous problem. We can scan each row and at the same time store how many continuous 1's we have met for each column. And then this problem will be finding maximum rectangle at each row. Below is an example:

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

And the accumulative table for this matrix is:

1	0	0	1
0	1	1	0
0	2	2	0
0	0	0	0

Hence we can conclude that the maximum area is 2+2, which is 4.

C++ Code:

/*
 * func: maximal_rectangle
 * goal: find the largest rectangle containing all ones
 * @param matrix: 2D input matrix
 * return: area of the maximal rectangle
 */
/*
 * we can create a helper matrix which store the number of continuous one's in each column until current row.
 * Then the job is as the problem of find the largest rectangle in a histogram
 * complexity: time O(mn), space O(mn)
 */
int maximalRectangle(vector<vector<char> > &matrix){
    if(matrix.size() == 0){
        return 0;
    }
    vector<vector<int> > helper_matrix(matrix.size(), vector<int>(matrix[0].size(), 0));
    
    //Compute continuous 1's numbers in each column
    for(int i = 0; i < matrix.size(); ++i){
        for(int j = 0; j < matrix[0].size(); ++j){
            if(i == 0){
                helper_matrix[i][j] = matrix[i][j] - '0';
            }else if(matrix[i][j] == '0'){
                helper_matrix[i][j] = 0;
            }else if(matrix[i][j] == '1'){
                helper_matrix[i][j] = helper_matrix[i-1][j] + 1;
            }
        }
    }
    
    //Compute the maximum area accumulated at each row
    int max_area = 0;
    for(int i=0; i<helper_matrix.size(); ++i){
        max_area = max(max_area, largest_rectangle_area(helper_matrix[i]))
    }
    
    return max_area;
}

Python Code:

# func: find the largest rectangle in a matrix
# @param matrix: input matrix
# @return: maximal area of the rectangle
# complexity: time O(mn), space O(mn)
def largest_rectangle(matrix):
    if len(matrix) == 0:
        return 0

    helper_matrix = [[0] * len(matrix[0]) for _ in xrange(len(matrix))]

    for i in xrange(len(matrix)):
        for j in xrange(len(matrix[0])):
            if i == 0:
                helper_matrix[i][j] = int(matrix[i][j])
            elif matrix[i][j] == '0':
                helper_matrix[i][j] = 0
            elif matrix[i][j] == '1':
                helper_matrix[i][j] = helper_matrix[i-1][j] + 1

    max_area = 0
    for i in xrange(len(helper_matrix)):
        max_area = max(max_area, largest_rectangle_area(helper_matrix[i]))

    return max_area