Given list of numbers find for each number in the list the next distinct number 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.
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} &lt; 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.