# 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? May 13 '18 at 11:09
• Can you explain the linear time algorithm? 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.