Tuesday, November 20, 2012

Solving Maximal Rectangle Problem based on "Largest Rectangle in Histogram" Problem

First of all, we get two problems here.
1. The Maximal Rectangle Problem and a good step-by-step solution
     The author presents there illustrates a number of principles that are widely applicable in algorithm design.
2. Largest Rectangle in Histogram Problem.
     If you are a Chinese guy, you can get a better understanding at Wangsishuang's Blog.

Then, how are these two problems here related?
Let's look at the Largest Rectangle in Histogram Problem first.
For example:
Given array [2,1,5,6,2,3] which represents the following histogram:




The Expected "Largest Rectangle" in this histogram is in shaded area which equals 10 unit.





As I stated at the beginning, there's O(n) solution for this problem by taking advantage of stacks. I'm not going to the details of that algorithm, assuming we now have a function 


int findMax(int[] heights)

which can get the max rectangle area in the histogram in O(n) time, then we can easily solve the Maximal Rectangle Problem  . How? 




We need to construct an assistant matrix to help us record the "histogram" of each row. As shown in the red rectangle, the corresponding row in the assistant matrix is the histogram of that row in the original matrix.


Then we just need to process the input matrix row by row, and for each row, we use findMax function to calculate the largest rectangle area:

public int maximalRectangle(int[][] matrix) {
        if(matrix.length<1)
            return 0;
       
        int maxRectangle = 0;
        int[][] cache = new int[matrix.length][matrix[0].length];
        for(int i=0;i<matrix.length;i++){
            for(int j=0;j<matrix[0].length;j++){
                if(matrix[i][j]==0)
                    cache[i][j]=0;
                else{
                    if(i>0)
                        cache[i][j]=cache[i-1][j]+1;
                    else
                        cache[i][j]=1;
                }
            }
            int rowMax = findMax(cache[i]);
            if(rowMax>maxRectangle)
                maxRectangle = rowMax;
        }
        return maxRectangle;
}

The outer loop is O(m) (m=no. of rows) and the inner loop is O(n) (n=no. of columns). Therefore the total runtime complexity is O(mn).


The Youtube video link I gave at the beginning shows how can we program the findMax function. And I paste it here:
private int findMax(int[] height){
        Stack<Integer> heights = new Stack<Integer>();
        Stack<Integer> indices = new Stack<Integer>();
        int max = 0;
        int lastIndex = 0;
       
        for(int i=0;i<height.length;i++){
            if(heights.empty() || height[i]>heights.peek()){ //current > top,just push in
                heights.push(height[i]);
                indices.push(i);
            }else if(height[i]<heights.peek()){ //current < top
                while(!heights.empty() && heights.peek()>height[i]){
                    lastIndex=indices.pop();
                    int temp = heights.pop();
                    if((i-lastIndex)*temp > max)
                        max = (i-lastIndex)*temp;
                }
               
                heights.push(height[i]);
                indices.push(lastIndex);
            }
            //note:if current = top , just ignore it.
        }
        /**
         * note: after processing, there still maybe elements in the stack.
         *       but they MUST BE in ascending order in the stack from bottom to top.
         */
        while(!heights.empty()){
            int temp = (height.length-indices.pop())*heights.pop();
            if(temp>max)
                max = temp;
        }
        return max;    
}

That's pretty much my general idea. In order to make it more efficient, we can merge findMax function into our maximalRectangle(). Therefore we don't need to create new stacks by scanning each row. And we don't need to traversal each row twice either. 

You can try these two problems on Leetcode Online Judge.
There are also some other variations of Rectangle Problem 

2 comments: