# My answer was accepted in 88ms, but i'm not sure about it's time complexity

• For every integer j between f[i] and i, we have height[j] >= height[i]. For every integer j between i and b[i], we have height[j] >= height[i]. And of course, among all possible integers, f[i] is the smallest one while b[i] is the largest one.
I think the time complexity of this algorithm is O(n), but I'm not sure.

``````int largestRectangleArea(vector<int> &height) {
int n = height.size();

if (n == 0) return 0;

vector<int> f(n), b(n);

f[0] = -1;
for (int i = 1; i < n; ++ i) {
f[i] = i-1;
while (f[i] != -1 && height[f[i]] >= height[i]) {
f[i] = f[f[i]];
}
}
b[n-1] = n;
for (int i = n-2; i > -1; -- i) {
b[i] = i+1;
while (b[i] != n && height[b[i]] >= height[i]) {
b[i] = b[b[i]];
}
}

int maxval = height[0];
for (int i = 1; i < n; ++ i) {
maxval = max(maxval, height[i]*(b[i]-f[i]-1));
}

return maxval;
}``````

• O(n) time complexity as every bar is visited in constant number of times relative to input list size.

• Could you explain it in a clearer way? Suppose there exists a strictly non-decreasing subsequence from position i to j and height[j+1] < height[i], then it'll take at least O(j-i) of time to calculate f[j+1] since for each k between i+1 and j, f[k] = k-1. It takes O(1) time to caculate each f[k] (i+1 <= k <= j), though. I suppose the average visited times of each bar is 2, am I right?

• yes; as the average visited time for each is bar is constant relative to input size; program runs in O(n) time complexity

• I believe your algorithm is not O(n) since there are two while's in the for loop. However, it is not that worse to O(n^2) since f[i] or b[i] decrease / increase very fast to end the while. Maybe the exact complexity can be proved. I guess is something like O(nlogn)

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