# 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.

• 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? – Yuval Filmus May 13 '18 at 11:09
• Can you explain the linear time algorithm? – saikiranboga May 13 '18 at 11:24

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.