Given a sequence of numbers $l_1, \ldots, l_n$, I want to find for each index $i$ the next possible number to the right of $l_i$ (if any) that is different from $l_i$. What is the best time and space optimal solution to do this?

The numbers may be repeating and are in no particular order.

  • $\begingroup$ You can easily construct the answer array $a_1,\ldots,a_n$ in linear time and using $O(1)$ auxiliary space. Is that what you're looking for? $\endgroup$ May 13, 2018 at 11:09
  • $\begingroup$ Can you explain the linear time algorithm? $\endgroup$ May 13, 2018 at 11:24

1 Answer 1


Here is pseudocode for an algorithm which outputs the entire answer array $a_1,\ldots,a_n$:

Set $\mathit{first} \gets 1$ (first index in the current run)

Set $\mathit{curr} \gets 1$ (index of the current element being scanned)

While $\mathit{curr} < n$:

   Set $\mathit{curr} \gets \mathit{curr} + 1$

   If $l_{\mathit{curr}} \neq l_{\mathit{first}}$:

     Set $a_{\mathit{first}},\ldots,a_{\mathit{curr}-1} \gets l_{\mathit{curr}}$

     Set $\mathit{first} \gets \mathit{curr}$

   End If

End While

Set $a_{first},\ldots,a_n \gets \bot$ (no different element to the right)

This algorithm uses linear time and $O(1)$ auxiliary space.


Your Answer

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

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