How to do it in less than O(n^2)


#1

I did it in O(n^2) but the line says you can do it in less than that as well. Is there a way , if yes please share. Here is my code for O n^2 time:
int f(vector arr,int n){
int res = 0,curr = 0,i = 0;
stack s;
while(i<n){
if(s.empty()||arr[s.top()]<=arr[i])
s.push(i++);
else{
int x = s.top();s.pop();
curr = arr[x](s.empty()?i:(i-s.top()-1));
res = max(res,curr);
}
}
while(!s.empty()){
int x = s.top();s.pop();
curr = arr[x]
(s.empty()?i:(i-s.top()-1));
res = max(res,curr);
}
return res;
}
int Solution::maximalRectangle(vector<vector > &A) {
int n = A.size(),m = A[0].size();
int res = f(A[0],m);int curr = 0;
for(int i=1;i<n;i++){
for(int j=0;j<m;j++){
if(A[i][j]==1)A[i][j]+=A[i-1][j];
}
}
for(int i=1;i<n;i++)
res = max(res,f(A[i],m));
return res;
}


#2

No, it can’t be done in less than O(n^2) time (where n is the number of rows or columns) in the worst case. This is because, at the very least, we have to visit all the elements to know whether they are 0 or 1, to include in our rectangle.