Evolve from brute force to optimal


  • 1

    This problem is similar to maximal square but much more difficult.

    1. brute force O(n^6), count each rectangle
        int maximalRectangle(vector<vector<char>>& matrix) {
            if(matrix.empty()) return 0;
            int r = matrix.size(), c = matrix[0].size(), area = 0;
            for(int i=0;i<r;i++)
                for(int j=0;j<c;j++) { //each start point (i,j)
                    if(matrix[i][j]=='0') continue;
                    for(int p=i;p<r;p++)
                        for(int q=j;q<c;q++) { // each end point (p,q)
                            if(matrix[p][q]=='0') continue;
                            bool ones = 1;
                            for(int x=i;x<=p;x++) {   //check if the rectangle contains all 1s
                                for(int y=j;y<=q;y++) 
                                    if(matrix[x][y] == '0') {
                                        ones = 0;
                                        break;
                                    }
                                if(!ones) break;
                            }
                            if(ones) area = max(area, (p-i+1)*(q-j+1));
                        }
                }
            return area;
        }
    
    1. O(n^4), whether a rectangle contains all 1s can be determined incrementally from the previous rectangle
        int maximalRectangle(vector<vector<char>>& matrix) {
            if(matrix.empty()) return 0;
            int r = matrix.size(), c = matrix[0].size(), area = 0;
            for(int i=0;i<r;i++)
                for(int j=0;j<c;j++) {
                    vector<vector<bool>> dp(r,vector<bool>(c));
                    for(int p=i;p<r;p++)
                        for(int q=j;q<c;q++) {
                            dp[p][q] = matrix[p][q]=='1';
                            if(p>i) dp[p][q] = dp[p][q] & dp[p-1][q];
                            if(q>j) dp[p][q] = dp[p][q] & dp[p][q-1];
                            if(dp[p][q]) area=max(area,(p-i+1)*(q-j+1));
                            else break;
                        }
                }
            return area;
        }
    
    1. O(n^3), for a start/end point, we do not need to consider all end/start points, we only need to consider points that connect to the start/end point by all 1s. We use a 2d array to cache number of consecutive 1s to the left of each point. Then for a point, we can determine its maximal rectangles in linear time. The idea is from @uniqueness .
        int maximalRectangle(vector<vector<char>>& matrix) {
            int r = matrix.size();
            if (!r) return 0;
            int c = matrix[0].size(), area = 0;
            vector<vector<int>> ones(r,vector<int>(c));
            for(int i=0;i<r;i++) 
                for(int j=0;j<c;j++) {
                    if(matrix[i][j]=='0') continue;
                    int w = ones[i][j] = (j?ones[i][j-1]:0) + 1;
                    for(int k=i; k>=0; k--) {
                        w = min(ones[k][j],w);
                        area = max(area,w*(i-k+1));
                    }
                }
            return area;
        }
    
    1. O(n^2) dp. The optimal solution does not check a rectangle by start/end point. Given a point (i, j), it computes the left boundary, right boundary of the maximal rectangle with height(i,j) incrementally in constant time. The idea is from @morrischen2008.
        int maximalRectangle(vector<vector<char>>& matrix) {
            int r = matrix.size();
            if (!r) return 0;
            int c = matrix[0].size(), area = 0;
            vector<int> left(c), right(c,c), height(c);
            for(int i=0;i<r;i++) { 
                int cur = 0;
                for(int j=0;j<c;j++)
                    if(matrix[i][j]=='0') {
                        height[j] = left[j] = 0;
                        cur = j+1; //left boundary of current row
                    } else {
                        left[j] = max(left[j],cur);  //left boundary for height[j]
                        height[j]++;
                    }
                cur = c;
                for(int j=c-1;j>=0;j--) {
                    if (matrix[i][j]=='0') cur = j;
                    right[j] = matrix[i][j]=='0'? c:min(right[j],cur);
                    area = max(height[j]*(right[j]-left[j]),area);
                }
            }
            return area;
        }
    

Log in to reply
 

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