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

• 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;
}
}
``````

• 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

• 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;
}
``````

}

• thanks a lot!!!

• Last fake column +1.

• 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;
}
};``````

• 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.

• Thanks for the reply.. Let me try that.

• This post is deleted!

• this is a great idea!

• Are you a genius...?

• 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;
}
};
``````

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

• 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.

• 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.

• 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

• ``````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;
}
``````

• ingenious...

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

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