Given list of numbers find for each number in the list the next distinct number

Question

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.

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.