Maximal rectangle with 1’s in a binary matrix (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.

Thoughts:
If we think the matrix as a number of rows and each row is a histogram then we can reduce the problem to the Largest Rectangle in Histogram problem. So how can we view each row as histogram? Consider the following binary matrix:

11000
11000
00111
00111
00111

The largest rectangle should be 3*3, apparently. What makes up a rectangle? There are 3 columns there, if you like, and each of them contains 3 consecutive ones. So if for each row, we count how many consecutive ones we have above us, we can construct 5 histograms:

11000
22000
00111
00222
00333

Then we can compute the largest rectangle for each row and we will find out that the last row contains a maximal rectangle with area of 5 in its histogram.

Code (Java):

import java.util.Stack;
public class Solution {
    public int maximalRectangle(char[][] matrix) {
        if(matrix.length == 0) 
            return 0;
        int[][] auxillary = new int[matrix.length][matrix[0].length];
        for(int i = 0; i < matrix.length; ++i) {
            for(int j = 0; j < matrix[i].length; ++j) {
                auxillary[i][j] = Character.getNumericValue(matrix[i][j]);
            }
        }
        for(int i = 1; i < auxillary.length; ++i) {
            for(int j = 0; j < auxillary[i].length; ++j) {
                if(auxillary[i][j] == 1)
                    auxillary[i][j] = auxillary[i-1][j] + 1;
            }
        }
        
        int max = 0;
        for(int i = 0; i < auxillary.length; ++i) {
            max = Math.max(max, largestRectangleArea(auxillary[i]));
        }
        return max;
    }
    
    private int largestRectangleArea(int[] height) {
        Stack<Integer> stack = 
            new Stack<Integer>();
        int max = 0;
        int i = 0;
        while(i < height.length) {
            if(stack.isEmpty() || 
                height[i] >= stack.peek()) {
                stack.push(height[i]);
                i++;
            }
            else {
                int count = 0;
                while(!stack.isEmpty() && 
                    stack.peek() > height[i]) {
                    count++;
                    int top = stack.pop();
                    max = Math.max(max, top * count);
                }
                for(int j = 0; j < count + 1; ++j) {
                    stack.push(height[i]);
                }
                i++;
            }
        }
        
        int count = 0;
        while(!stack.isEmpty()) {
            count++;
            max = Math.max(max, stack.pop() * count);
        }
        return max;
    }
}

Code (C++):

class Solution {
public:
    int maximalRectangle(vector<vector<char> > &matrix) {
        if(matrix.size() == 0) 
            return 0;
        vector<vector<int> > auxillary;
        for(int i = 0; i < matrix.size(); ++i) {
            vector<int> temp;
            for(int j = 0; j < matrix[i].size(); ++j) {
                temp.push_back(matrix[i][j] - '0');
            }
            auxillary.push_back(temp);
        }
        for(int i = 1; i < auxillary.size(); ++i) {
            for(int j = 0; j < auxillary[i].size(); ++j) {
                if(auxillary[i][j] == 1)
                    auxillary[i][j] = auxillary[i-1][j] + 1;
            }
        }
        
        int maxArea = 0;
        for(int i = 0; i < auxillary.size(); ++i) {
            maxArea = max(maxArea, largestRectangleArea(auxillary[i]));
        }
        return maxArea;
    }
    
private:
    int largestRectangleArea(vector<int> &height) {
        stack<int> stack_;
        int maxArea = 0;
        int i = 0;
        while(i < height.size()) {
            if(stack_.empty() || 
                height[i] >= stack_.top()) {
                stack_.push(height[i]);
                i++;
            }
            else {
                int count = 0;
                while(!stack_.empty() && 
                    stack_.top() > height[i]) {
                    count++;
                    int top = stack_.top();
                    stack_.pop();
                    maxArea = max(maxArea, top * count);
                }
                for(int j = 0; j < count + 1; ++j) {
                    stack_.push(height[i]);
                }
                i++;
            }
        }
        
        int count = 0;
        while(!stack_.empty()) {
            count++;
            maxArea = max(maxArea, stack_.top() * count);
            stack_.pop();
        }
        return maxArea;
    }
};
Advertisements

5 Comments (+add yours?)

  1. AprilBasil
    Dec 01, 2012 @ 15:45:55

    Java solution for “Maximal rectangle with 1’s in matrix”, cannot pass Leet OJ for large data. TLE

    Reply

  2. anurag
    Feb 07, 2013 @ 06:25:01

    plz snd me dis java program with main() on my email lck.malhotra@gmail.com

    Reply

  3. natural vitiligo treatment system ebook download
    Mar 04, 2013 @ 11:47:09

    Hi! Someone in my Facebook group shared this website with us so I came to take a look.
    I’m definitely loving the information. I’m book-marking and will be tweeting this to my followers!

    Outstanding blog and superb style and design.

    Reply

  4. intelligent cruiser tips
    Jul 19, 2013 @ 15:37:44

    Fantastic post but I was wanting to know if you could write a litte more on this
    topic? I’d be very thankful if you could elaborate a little bit further. Thank you!

    Reply

  5. mobile games
    Apr 15, 2014 @ 05:16:26

    Interesting blog! Is your theme custom made or did you download it from somewhere?

    A theme like yours with a few simple adjustements would really make my blog shine.
    Please let me know where you got your design. Appreciate
    it

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: