We have an array of $n$ positive integers $a_0,a_1\dots a_{n-1}$ and let $a_n=0$.
I need to build an array $b_0,b_1\dots b_{n-1}$ such that $b_i$ is the first integer larger than $i$ with $a_{b_i}\leq a_i$. (Note that there is no requirement that the $b_i$ be distinct.)
Does anybody know if this can be done in reasonable time? (say $\mathcal O(n\log n)$ for example)
There is an $O(n)$ solution for building such array using stack.
Starting with a brute force algorithm, you can traverse the array from right to left and for each element in the array, try all elements to the right of it until finding a smaller number. That would be $O(n^2)$.
To get an $O(n)$ solution, instead of each element having to look at all the elements to the right of it. We would just maintain a list of special elements by noticing that whenever a number at position $x$ sees a larger number to the right of it (at position $y$ where $y$ > $x$), the larger number is of no use anymore.
To prove that, we can assume for contradiction that element at position y was the $b_i$ of some future number. That means that $a_y < a_i$ but since $a_x < a_y < a_i$ and $x$ is between $i$ and $y$, then element $x$ would have been $b_i$ instead. Hence, a contradiction.
The algorithm to get $b_i$ would be to do the same as the brute force, but instead of just searching for a smaller element to the right, we will delete the larger elements that we meet on our way and break as soon as we find a smaller number. Simulating this efficiently can be done using a stack, where each $i$ keeps popping elements while the top of the stack is larger than $a_i$. The top of the stack after the pops will be $b_i$. $a_i$ is then pushed to the stack so that it will be seen by the next elements.
The algorithm may still look as an $O(n^2)$ algorithm, but looking at the number of times that an array element is checked, we will find that each element is looked at for a constant number of times, since it is either pushed (once), popped (also once) or selected as $b_i$ (total of n for all a $b_i$). So the sum of operations is $O(n)$ for the algorithm.
