A O(n^2) solution based on Largest Rectangle in Histogram


  • 195
    W

    This question is similar as [Largest Rectangle in Histogram]:

    You can maintain a row length of Integer array H recorded its height of '1's, and scan and update row by row to find out the largest rectangle of each row.

    For each row, if matrix[row][i] == '1'. H[i] +=1, or reset the H[i] to zero.
    and accroding the algorithm of [Largest Rectangle in Histogram], to update the maximum area.

    public class Solution {
        public int maximalRectangle(char[][] matrix) {
            if (matrix==null||matrix.length==0||matrix[0].length==0)
                return 0;
            int cLen = matrix[0].length;    // column length
            int rLen = matrix.length;       // row length
            // height array 
            int[] h = new int[cLen+1];
            h[cLen]=0;
            int max = 0;
            
            
            for (int row=0;row<rLen;row++) {
                Stack<Integer> s = new Stack<Integer>();
                for (int i=0;i<cLen+1;i++) {
                    if (i<cLen)
                        if(matrix[row][i]=='1')
                            h[i]+=1;
                        else h[i]=0;
                    
                    if (s.isEmpty()||h[s.peek()]<=h[i])
                        s.push(i);
                    else {
                        while(!s.isEmpty()&&h[i]<h[s.peek()]){
                            int top = s.pop();
                            int area = h[top]*(s.isEmpty()?i:(i-s.peek()-1));
                            if (area>max)
                                max = area;
                        }
                        s.push(i);
                    }
                }
            }
            return max;
        }
    }
    

  • 0
    S

    It's a great idea. Thanks for sharing. In case it might be also helpful to others, I'm just adding some notes here regarding the array H.

    It records the current height of columns during the loop of rows, where the height is defined as:

    for row of index `row`, the consecutive number of 1's from `row` to `0`
    

    As it is mentioned, the height for column i H[i] is reset to 0 where matrix[row][i] is 0 while looping through row.

    I also like the trick you use for the last fake column H[cLen]. =)

    For reference: linear solution to largest rectangle in histogram


  • 2
    R

    This is a great solution. My solution has the same idea while it includes a trick to avoid check if the stack is empty.

    public class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix==null||matrix.length==0)
            return 0;
        if (matrix[0]==null||matrix[0].length==0)
            return 0;
            
        int[] record = new int[matrix[0].length];
        Arrays.fill(record,0);
        int result = 0;
    
        Stack<Integer> index = new Stack<Integer>();
        index.push(-1);
    
        for (int i=0;i<matrix.length;i++){
            for (int j=0;j<matrix[0].length;j++){
                if (matrix[i][j]=='1')
                    record[j]+=1;
                else
                    record[j]=0;
    
                while(index.peek()>-1)
                    if (record[index.peek()]>record[j]){
                        int top=index.pop();
                        result=Math.max(result,record[top]*(j-index.peek()-1));
                    }
                    else break;
                    
                index.push(j);
            }
            while(index.peek()>-1){
                
                int top=index.pop();
                if (record[top]>0)
                    result=Math.max(result,record[top]*(matrix[0].length-index.peek()-1));
            }
        }
        return result;    
    }
    

    }


  • 0
    S

    thanks a lot!!!


  • 0
    L

    Last fake column +1.


  • 0

    I converted the code to c++ but cannot figure out why it cannot passed the case. I really can't see any differences between the Java code and the C++ code. The only significant change I made is

    in Java:

    int top = s.pop();
    

    Change in C++

    int top = s.top(t);
    s.pop();
    

    Why it is keep complaining the case below but passed in Java? Thanks in advance.

    Input: ["1"]
    Output: 0
    Expected: 1

    class Solution {
    public:
        int maximalRectangle(vector<vector<char> > &matrix) {
    		if (matrix.empty() || matrix.size() == 0 || matrix[0].size() == 0)
    			return 0;
    	
    		int cLen = matrix[0].size();
    		int rLen = matrix.size();
    		
    		int h[cLen+1];
    		int max = 0;
    		
    		for (int row = 0; row < rLen; row++) {
    			stack<int> s;
    			for (int i = 0; i < cLen + 1; i++) {
    				if (i < cLen) {
    					if (matrix[row][i] == '1') h[i] += 1;
    					else h[i] = 0;		
    				}
    				
    				if (s.empty() || h[s.top()] <= h[i]) 
    				    s.push(i);
    				else {
    					while (!s.empty() && h[i] < h[s.top()]) {
    						int top = s.top(t);
    						s.pop();
    						int area = h[top] * (s.empty() ? i: (i - s.top() - 1));
    						
    						if (area > max) max = area;
    					}
    					s.push(i);
    				}
    			}
    		}
    		return max;
        }
    };

  • 0
    D

    If you print the value of the h[i], you could find that some value is undefined.You may add some line to initial the h.


  • 0

    Thanks for the reply.. Let me try that.


  • -8
    L
    This post is deleted!

  • 0
    L

    this is a great idea!


  • 0

  • 0
    T

    Are you a genius...?


  • 1
    J

    Good idea. Here is my C++ version:

    class Solution {
    public:
        int maximalRectangle(vector<vector<char>> &matrix) {
            if (matrix.empty()) return 0;
            int rows = matrix.size();
            int cols = matrix[0].size();
            int maxArea = 0;
            vector<int> heights(cols + 1, 0);
            vector<int> stack;
            for (int i = 0; i < rows; i++) {
                stack.clear();
                for (int j = 0; j < cols + 1; j++) {
                    if (j < cols) {
                        if (matrix[i][j] == '1') {
                            heights[j]++;
                        } else {
                            heights[j] = 0;
                        }
                    }
                    if (stack.empty() || heights[j] >= heights[stack.back()]) {
                        stack.push_back(j);
                        continue;
                    }
                    while (!stack.empty() && heights[j] < heights[stack.back()]) {
                        int top = stack.back();
                        stack.pop_back();
                        int begin = stack.empty() ? 0 : stack.back() + 1;
                        int area = heights[top] * (j - begin);
                        if (area > maxArea) maxArea = area;
                    }
                    stack.push_back(j);
                }
            }
            return maxArea;
        }
    };
    

  • 0
    J

    What a neat solution! That fake last column is awesome :)


  • 0
    D

    I don't understand your solution. There are n^2 possible combination of h array. solving one h array needs O(n) time, so the solution should require O(n^3) running time. It seems to me you solution only consider n possible combination of h array, which seems wrong.


  • 0
    D

    I don't understand your solution. There are n^2 possible combination of h array. solving one h array needs O(n) time, so the solution should require O(n^3) running time. It seems to me you solution only consider n possible combination of h array, which seems wrong.


  • 1
    T

    Danielgaoys, the algorithm is updating array "h" by doing "h[i]+=1", which means accumulated height so far. So, do not need to consider n^2 combination


  • 24
    S
    the same idea, but more concise    
    
    int maximalRectangle(vector<vector<char> > &matrix) {
        if (matrix.size() <= 0 || matrix[0].size() <= 0)
            return 0;
            
        int m = matrix.size();
        int n = matrix[0].size() + 1;
        int h = 0, w = 0, ret = 0;
        vector<int> height(n, 0);
        
        for (int i = 0; i < m; ++i) {
            stack<int> s;
            for (int j = 0; j < n; ++j) {
                // set value
                if (j < n - 1) {
                    if (matrix[i][j] == '1') height[j] += 1;
                    else height[j] = 0;
                }
                
                // compute area
                while (!s.empty() && height[s.top()] >= height[j]) {
                    h = height[s.top()];
                    s.pop();
                    w = s.empty() ? j : j - s.top() - 1;
                    if (h * w > ret) ret = h * w;
                }
                
                s.push(j);
            }
        }
        
        return ret;
    }
    

  • 0
    X

    ingenious...


  • 0
    S

    The algorithm is O(n^2). The h array is updated each row instead of a new one.


Log in to reply
 

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