2
$\begingroup$

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)

$\endgroup$
4
  • $\begingroup$ now that I think about it there is a $n\log^2(n)$ solution using binary search and a range minimum query, but that seems like a drag to implement, perhaps there is something simpler? $\endgroup$ – user26358 Jul 17 '16 at 20:52
  • $\begingroup$ You can get $O(n\log n)$ using a balanced binary tree. Go backwards over the data. $\endgroup$ – Yuval Filmus Jul 17 '16 at 20:57
  • $\begingroup$ what do you mean go backwards over the data? $\endgroup$ – user26358 Jul 17 '16 at 23:27
  • $\begingroup$ This question is a duplicate of cs.stackexchange.com/questions/48500/… $\endgroup$ – KWillets Jul 18 '16 at 22:47
1
$\begingroup$

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.

Complexity

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.

$\endgroup$
1
  • $\begingroup$ Wow, this is awesome, thanks so much! I love you. $\endgroup$ – user26358 Jul 18 '16 at 3:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy