4
$\begingroup$

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?

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

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$

$\endgroup$

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.