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?
7
-
$\begingroup$ No, the problem is essentially equivalent to sorting, so it cannot in O(k) $\endgroup$– jmsterCommented May 21, 2017 at 7:12
-
$\begingroup$ @jmster Care to elaborate? $\endgroup$– Yuval FilmusCommented 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$– shmthCommented 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$– AryabhataCommented May 23, 2017 at 19:52
-
$\begingroup$ @Aryabhata I meant the former. Can you explain the linear time algorithm? $\endgroup$– shmthCommented May 24, 2017 at 8:48
|
Show 2 more comments
1 Answer
$\begingroup$
$\endgroup$
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$
answered May 26, 2017 at 20:53