1
$\begingroup$

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.

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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