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?

  • $\begingroup$ No, the problem is essentially equivalent to sorting, so it cannot in O(k) $\endgroup$
    – jmster
    Commented May 21, 2017 at 7:12
  • $\begingroup$ @jmster Care to elaborate? $\endgroup$ Commented May 21, 2017 at 7:45
  • $\begingroup$ @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 $\endgroup$
    – shmth
    Commented May 21, 2017 at 8:09
  • $\begingroup$ 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. $\endgroup$
    – Aryabhata
    Commented May 23, 2017 at 19:52
  • $\begingroup$ @Aryabhata I meant the former. Can you explain the linear time algorithm? $\endgroup$
    – shmth
    Commented May 24, 2017 at 8:48

1 Answer 1


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$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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