# How to find nearest number in a sequence that is strictly smaller than given number

Given a sequence of numbers $l_1, \ldots, l_k$, I want to find for each $i$ the nearest numbers to the left and right of $l_i$ (if any) that are strictly smaller than $l_i$. Is it possible to do this in linear time?

• No, the problem is essentially equivalent to sorting, so it cannot in O(k) – jmster May 21 '17 at 7:12
• @jmster Care to elaborate? – Yuval Filmus May 21 '17 at 7:45
• @jmster I am reading the paper here: eprints.library.iisc.ernet.in/60/1/COLE.pdf and in section 8 paragraph 4, it talks about something like what i am trying to do. Of course the scenario in the paper is a bit different but it seems like you would still need to be able to solve this problem inlinear time – shmth May 21 '17 at 8:09
• What does nearest mean? $l_j \lt l_i$ such that $|i - j|$ is smallest or $|l_i - l_j|$ is smallest? If the former, there is a linear time algorithm. – Aryabhata May 23 '17 at 19:52
• @Aryabhata I meant the former. Can you explain the linear time algorithm? – shmth May 24 '17 at 8:48

## 1 Answer

Converting my comment into an answer.

Here is an algorithm for the interpretation that you are looking for $l_j$ such that $l_j \lt l_i$ and $|i-j|$ is the smallest.

Traverse left to right, push stuff on stack. If new element to be pushed >= top element. If new element < top element keep popping the stack till top < new element. For the elements popped, the new element is the $l_j$