# My 16ms C++ O(n) code without a stack

• Basically, I find the range (left[i], right[i]) within which the height of every element is at least height[i]. For each i, there is a rectangular with area height[i] * (right[i]-left[i]+1), and the largest area must be one of them. Then run all i to find the largest area. Please notice it takes O(n) time to fill left[i] and right[i] if we use DP. We can use amortization analysis to find this out. If you think about the worst case for a certain i, if it takes k steps in the while loop to get left[i]. Then it means there are k indices (for each j update below) which only take 1 step each in the loop to find left item for these indices. Then the average number of steps of these k+1 indices is const. So it takes O(n) to fill left and right arrays.

``````class Solution {
public:
int largestRectangleArea(vector<int>& height) {
int N=height.size(), i, j, l, r, area=0, temp;
if(N==0) return 0;
vector<int> left(N), right(N);
left[0]=0;  //fill left[i] in the for loop
for(i=1; i<N; ++i){
l=i;
j=i-1;
while(j>=0&&height[j]>=height[i]){   // amortization shows const steps for this loop
if(height[j]==height[i]){
l=left[j];
break;
}
l=left[j];
j=left[j]-1;
}
left[i]=l;
}
right[N-1]=N-1;  //fill right[i] in the for loop
for(i=N-2; i>=0; --i){
r=i;
j=i+1;
while(j<N && height[j]>=height[i]){
if(height[j]==height[i]){
r=right[j];
break;
}
r=right[j];
j=right[j]+1;
}
right[i]=r;
}
for(i=0; i<N; ++i){
temp=height[i]*(right[i]-left[i]+1);
if(temp>area) area = temp;
}
return area;
}
};``````

• what is the time complexity? is it O(N^2)?

• It is O(n^2). Consider the worst case growing from small to big, the number in the middle is INT_MAX -1, then the other half decreases from big to small. It is o(n/2) + o(n/2)*o(n/2) ~ O(n^2)

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