# Why dp is much faster than stack?

• I think both time complexity are O(m*n), where m is matrix.length, and n is matrix[0].length.
and dp based algorithm will traverse two more times than stack based algorithm each row. So I am confused about the fact that dp is much faster than stack. Can anyone help?

## DP based Algorithm: 10ms

``````public class Solution {
public int maximalRectangle(char[][] matrix) {
int m = matrix.length;
if(m == 0) return 0;

int n = matrix[0].length;
if(n == 0) return 0;

int maxRec = 0;

int [] left = new int[n];
int [] right = new int[n];
int [] height = new int[n];

for(int i = 0; i<n; ++i) right[i] = n;
for(int i = 0; i<m; ++i){
//calculate heights
for(int j = 0;j<n; ++j){
height[j] = matrix[i][j] == '0'? 0: height[j]+1;
}

int cur_left = 0;
for(int j = 0; j<n; ++j){
if(matrix[i][j] != '0') left[j] = Math.max(left[j], cur_left);
else{
left[j] = 0;
cur_left = j + 1;
}
}
int cur_right = n;
for(int j =n-1; j>=0; --j){
if(matrix[i][j] != '0') right[j] = Math.min(right[j], cur_right);
else{
right[j] = n;
cur_right = j;
}
}

for(int j = 0; j<n; ++j){
maxRec = Math.max(maxRec, height[j] *(right[j]-left[j]));
}
}
return maxRec;
}
}
``````

## Stack based Algorithm: 75ms

``````public class Solution {
public int maximalRectangle(char[][] matrix) {
int m = matrix.length;
if(m == 0) return 0;
int n = matrix[0].length;
if( n== 0) return 0;

int [] height = new int[n];
int maxRec = 0;
Stack<Integer> stack = new Stack<>();

stack.push(-1);
for(int i = 0;i<m;++i){
for(int j =0; j<n;++j){
height[j] = matrix[i][j]=='0'?0:height[j] +1;
while(stack.peek() != -1 && height[j] <= height[stack.peek()]){
int end = stack.pop();
maxRec = Math.max(maxRec, height[end] * (j-stack.peek()-1));
}
stack.push(j);
}

while(stack.peek() != -1){
int h = height[stack.pop()];
maxRec = Math.max(maxRec, h *(n-1-stack.peek()));
}
}
return maxRec;
}
}
``````

• @biwuxia You are using `stack object` instead of primitive array to store the heights, which can be the major reason. Perhaps you should try `int [] stack; int top=-1` instead of `Stack<Integer>`.

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