The problem goes as follows:
You are given an array a of N non-negative integers, indexed from 1 to N. Define prev(x) such that prev(x) is the largest integer that satifies both following conditions: prev(x) < x, and a[prev(x)] < x. Print prev(i) for each i from 1 to N.
This is a basic problem that can be solved using stacks. However, I've seen an interesting implementation that avoids data structures altogether. Here's the main code for it:
cin>>n;
for (int i=1; i<=n; ++i) cin>>a[i];
a[0]=-inf;
for (int i=1; i<=n; ++i){
int p=i-1;
while (a[p]>=a[i]) p=sol[p];
sol[i]=p;
}
for (int i=1; i<=n; ++i) cout<<sol[i]<<" "; cout<<"\n";
return 0;
It seems to me that this runs in O(n) on average, but I cannot find its worst-case complexity. I suspect it to be O(n^2) but have had no luck proving it so far (I once used this implementation in a practice problem and got TLEed). Any help would be greatly appreciated. Thanks!