85. Maximal Rectangle

Explanation

Firstly, we loop through the rows of matrix. Calculate the maximum area for that height.

Note that height is from row[0] to row[i], area = height * width.

Calculate width

To Calculate width, we have to find its right most position and its left most position with that specific height.

Here's when dynamic programming comes to play:

left most position calculation

from left to right:
    if true:
        inherit row[i-1] calculated left value,
        but note that there's also left limits in current row.
    else
        update left limit of current row & avoid next row inheritance.

right most position calulation is much simular.

and, since width = right - left, we can easily calculate the answer.

Code

cpp

int maximalRectangle(vector<vector<char>>& matrix) {
    int m = matrix.size(), n = matrix[0].size(), res = 0;
    array<int,200> left, right, height;
    left.fill(0), right.fill(n), height.fill(0);
    for(int i = 0; i < m; i++) {
        int ml = 0, mr = n;
        for(int j = 0; j < n; j++) {
            if(matrix[i][j] == '1') height[j]++;
            else height[j] = 0;
        }
        for(int j = 0; j < n; j++) {
            if(matrix[i][j] == '1') left[j] = max(left[j], ml);
            else left[j] = 0, ml = j+1;
        }
        for(int j = n-1; j >= 0; j--) {
            if(matrix[i][j] == '1') right[j] = min(right[j], mr);
            else right[j] = n, mr = j;
        }
        for(int j = 0; j < n; j++) {
            res = max(res, (right[j] - left[j]) * height[j]);
        }
    }
    return res;
}

Complexity Analysis

Time: O(m*n)

Space: O(n)

85. Maximal Rectangle ​

Explanation ​

Calculate width ​

Here's when dynamic programming comes to play: ​

Code ​

Complexity Analysis ​