Share my DP solution


  • 550
    M

    The DP solution proceeds row by row, starting from the first row. Let the maximal rectangle area at row i and column j be computed by [right(i,j) - left(i,j)]*height(i,j).

    All the 3 variables left, right, and height can be determined by the information from previous row, and also information from the current row. So it can be regarded as a DP solution. The transition equations are:

    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';

    height(i,j) = 0, if matrix[i][j]=='0'

    The code is as below. The loops can be combined for speed but I separate them for more clarity of the algorithm.

    class Solution {public:
    int maximalRectangle(vector<vector<char> > &matrix) {
        if(matrix.empty()) return 0;
        const int m = matrix.size();
        const int n = matrix[0].size();
        int left[n], right[n], height[n];
        fill_n(left,n,0); fill_n(right,n,n); fill_n(height,n,0);
        int maxA = 0;
        for(int i=0; i<m; i++) {
            int cur_left=0, cur_right=n; 
            for(int j=0; j<n; j++) { // compute height (can do this from either side)
                if(matrix[i][j]=='1') height[j]++; 
                else height[j]=0;
            }
            for(int j=0; j<n; j++) { // compute left (from left to right)
                if(matrix[i][j]=='1') left[j]=max(left[j],cur_left);
                else {left[j]=0; cur_left=j+1;}
            }
            // compute right (from right to left)
            for(int j=n-1; j>=0; j--) {
                if(matrix[i][j]=='1') right[j]=min(right[j],cur_right);
                else {right[j]=n; cur_right=j;}    
            }
            // compute the area of rectangle (can do this from either side)
            for(int j=0; j<n; j++)
                maxA = max(maxA,(right[j]-left[j])*height[j]);
        }
        return maxA;
    }
    

    };

    If you think this algorithm is not easy to understand, you can try this example:

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

    The vector "left" and "right" from row 0 to row 2 are as follows

    row 0:

    l: 0 0 0 3 0 0 0
    r: 7 7 7 4 7 7 7
    

    row 1:

    l: 0 0 2 3 2 0 0
    r: 7 7 5 4 5 7 7 
    

    row 2:

    l: 0 1 2 3 2 1 0
    r: 7 6 5 4 5 6 7
    

    The vector "left" is computing the left boundary. Take (i,j)=(1,3) for example. On current row 1, the left boundary is at j=2. However, because matrix[1][3] is 1, you need to consider the left boundary on previous row as well, which is 3. So the real left boundary at (1,3) is 3.

    I hope this additional explanation makes things clearer.


  • 0
    C

    This dp way is even more elegant than the stack solution!


  • 1
    M

    Nice solution, thanks for your sharing. But for right(i,j), it should be min(right(i-1,j), curright). You got it right in the code but a typo in the transition equations.


  • 1
    M

    Thanks for pointing out. The typo is fixed.


  • 157
    G

    This solution is so clever that I think so hard to understand it.
    height counts the number of successive '1's above (plus the current one). The value of left & right means the boundaries of the rectangle which contains the current point with a height of value height.


  • 0
    X

    Brilliant solution!


  • 0
    S
    This post is deleted!

  • 0
    P

    Beautiful method!!


  • 0
    M

    U r a genius really!!!!!!!


  • 0
    Z

    like this solution.


  • 0
    S

    really brilliant method!!!!


  • 0
    H

    Really amazing solution!!!


  • 0
    S

    Awesome, guy!


  • 0

    Incredible method!


  • 1
    H

    Salute Bro..


  • 4
    L

    Very neat solution. I rewrote it in C# by modifying them to a 2-d DP array

    public int MaximalRectangle(char[,] matrix) {
        int n = matrix.GetLength(1), maxA = 0;
        int[,] dp = new int[n, 3]; //[i, 0] is left; [i, 1] is right; [i, 2] is height
        for(int i = 0; i < n; i++) dp[i, 1] = n;
        for(int i = 0; i < matrix.GetLength(0); i++) {
            int cur_left = 0, cur_right = n;
            for(int j = 0; j < n; j++) { 
                if(matrix[i, j] == '1')     // compute height (can do this from either side)
                    dp[j, 2]++;
                else dp[j, 2]=0;
                if(matrix[i, j] == '1')     // compute left (from left to right)
                    dp[j, 0] = Math.Max(dp[j, 0], cur_left);
                else { dp[j, 0] = 0; cur_left = j + 1; }
            }
            // compute right (from right to left)
            for(int j = n - 1; j >= 0; j--) {
                if(matrix[i, j] == '1') dp[j, 1] = Math.Min(dp[j, 1], cur_right);
                else { dp[j, 1] = n; cur_right = j; }
            }
            // compute the area of rectangle (can do this from either side)
            for(int j = 0; j < n; j++)
                maxA = Math.Max(maxA, (dp[j, 1] - dp[j, 0]) * dp[j, 2]);
        }
        return maxA;
    }

  • 0
    D

    cool~!! 相当漂亮的DP!!


  • 3
    F

    I modified the boundary for the right side to make both direction consistent and confirmed to definition

    if(matrix.empty()) return 0;
    const int m = matrix.size();
    const int n = matrix[0].size();
    int left[n], right[n], height[n];
    fill_n(left,n,0); fill_n(right,n,n); fill_n(height,n,0);
    int maxA = 0;
    for(int i=0; i<m; i++) {
        int cur_left=0, cur_right=n-1; 
        for(int j=0; j<n; j++) { // compute height (can do this from either side)
            if(matrix[i][j]=='1') height[j]++; 
            else height[j]=0;
        }
        for(int j=0; j<n; j++) { // compute left (from left to right)
            if(matrix[i][j]=='1') left[j]=max(left[j],cur_left);
            else {left[j]=0; cur_left=j+1;}
        }
        // compute right (from right to left)
        for(int j=n-1; j>=0; j--) {
            if(matrix[i][j]=='1') right[j]=min(right[j],cur_right);
            else {right[j]=n-1; cur_right=j-1;}    
        }
        // compute the area of rectangle (can do this from either side)
        for(int j=0; j<n; j++)
            maxA = max(maxA,(right[j]-left[j]+1)*height[j]);
    }
    return maxA;

  • 0
    L
    This post is deleted!

  • 11

    Great code! I guess it would be easier to understand by also visualizing height for the above example :-)

    0th row: 0 0 0 1 0 0 0
    height: 0 0 0 1 0 0 0
    left: 0 0 0 3 0 0 0
    right 7 7 7 4 7 7 7
    
    1st row: 0 0 1 1 1 0 0
    height: 0 0 1 2 1 0 0 
    left: 0 0 2 3 2 0 0
    right: 7 7 5 4 5 7 7
    
    2nd row: 0 1 1 1 1 1 0
    height: 0 1 2 3 2 1 0
    left: 0 1 2 3 2 1 0
    right: 7 6 5 4 5 6 7
    

    Very nice to see the heights accumulate in height and the values of left and right updating in the loop.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.