## 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.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;
}
};

__ATA.cmd.push(function() {
__ATA.initVideoSlot('atatags-370373-5c910487b0b90', {
sectionId: '370373',
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-26942-5c910487b0bb8',  {
collapseEmpty: 'before',
sectionId: '26942',
width: 300,
height: 250
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-114160-5c910487b0bbb',  {
collapseEmpty: 'before',
sectionId: '114160',
width: 300,
height: 250
});
});

Related
```

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

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

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

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.

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!

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