leetcode Question 47: Maximal Rectangle

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.

Analysis:

This is not an easy problem and the idea is not straightforward.
Since the question requires the area of all ones region, first we can define the region (rectangle) in the matrix. Any region in the matrix has several basic properties:   1 corner point,  width, and length.
Also which corner point it is decide the exact place of the region, here we consider the bottom-right corner point, because we usually scan the matrix from (0,0) to right and down direction. For this problem, we also need to consider the "all ones" requirement, where all the regions are filled with 1s.

We can then have this data structure:
One 2D array(vector) ones[i][j],  where ones[i][j] stores the number of contiguous 1s ended at matrix[i][j], along ith row. e.g.  if matrix[i] = "1011101", then ones[i]=1,0,1,2,3,0,1. This array stores the length of the rectangle, for every possible bottom-right corner point.

Having this two values, next is to find the height of the rectangle, as well as keep the "all ones" requirement.
Start with a corner point [i][j],  since it is the bottom right corner, the rectangle search direction is left and up.
For the left we already have the number of contiguous 1s ones[i][j]. How to get the height?  We need to scan all the values above ones[i][j], it is from i-1 to 0. If meets 0, then stop, else compute the possible rectangle area, and store the max. To compute the area, the minimum length of rectangle should be compared and stores every time.

Details can be found in the code below, which passed all the small and big test cases.

Code(updated 201309):

class Solution {
public:
    int maximalRectangle(vector<vector<char> > &matrix) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int row = matrix.size();
        if (row==0){return 0;}
        int col = matrix[0].size();
        int res=0;
        vector<vector<int>> ones(row,vector<int>(col,0));
            
        for (int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if (matrix[i][j]=='1'){  
                    if (j==0){ones[i][j]=1;}
                    else{ones[i][j]=ones[i][j-1]+1;}
                }
            }
        }
        
        for (int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if (ones[i][j]!=0){  
                    int h = i-1;
                    int tmp=ones[i][j];
                    int mini=ones[i][j];
                    while (h>=0){
                        if (ones[h][j]==0){
                            break;
                        }else{
                            if (ones[h][j]<mini){
                                mini = ones[h][j];
                            }
                            if (tmp< mini*(i-h+1)){
                                tmp= mini*(i-h+1); 
                            }
                            h--;
                        }
                    }
                    if (res<tmp){
                        res=tmp;
                    }
                }
            }
        }
        
        return res;
    }
};
 


4 comments:

  1. Excuse for my little Ads.
    The O(n) algorithm can be found here (n is the size of matrix)
    http://fmarss.blogspot.com/2014/08/leetcode-solution-maximal-rectangle.html

    ReplyDelete
  2. Hi, could you please tell me how can I get to the coordinates of that rectangle saved in "res"? You know something like X,Y,H,W. Where X,Y are starting coords and H,W (heigth, width) are finishing coords.

    Sorry, but English is not my native language.
    Thanks for an answer.
    Bye.

    ReplyDelete
  3. My python code based on your algorithm got a TLE

    ReplyDelete
  4. Can you post a test/driver that constructs the matrix and reports the location and size of the maximal rectangle? That would definitely help out people that want to play with your solution :)

    ReplyDelete