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$
  • $\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$ – Jorge Fernández 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$ – Jorge Fernández 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
2
$\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$
  • $\begingroup$ Wow, this is awesome, thanks so much! I love you. $\endgroup$ – Jorge Fernández 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

Not the answer you're looking for? Browse other questions tagged or ask your own question.