Copying items in arrays while checking their indexes

Question

Array $P$ of length $n$ is a permutations of $\{0, ..., n-1\}$

Write a code, which would in $O(n)$ create an array $R$ of length $n$, so for values $x_i, x_j \in P$, $R[x_i] < R[x_j]$ if $x_i$ is on the left of $x_j$ ($i<j$).

This is a algorithmization problem that's recurring in the final's test each year and I'm stuck with it for weeks. I know that I'm supposed to show my work before asking here, but I didn't know how to start.

Could you at least point me to the right direction? What technique do I use, dynamic programming? Is this a problem for a specific algorithm?

Answer 1

All you're looking for is some mapping between the elements of $P$ and their indexes, that can be found in $O(1)$ for each element of $P$. Suppose given $p_i \in P$, you can use the fact that $p_i \in \{0, \dots n-1\}$, and that no $p_j \in P$ exists s.t $p_j = p_i$ (other than $j=i$).

How will you do it? Set $R[x]$ to the index of element $x \in P$.

• Since $x$ is unique, no elements of $R$ will be overridden.
• Suppose $p_i , p_j \in P$, and $p_i$ occures before $p_j$ ($i<j$). Then $R[p_i] = i$ and $R[p_j] = j$, and it holds that $R[p_i]<R[p_j]$

You should be able to take it from here.

Answer 2

Hint, try to determine which element of $R$ should be mapped to 0.

Then try to determine which element of $R$ should be mapped to 1. You will get the idea.

---

Here is the pseudocode.

Input: array $P[0], P[1], \cdots, P[n-1]$, which is a permutation of $0, 1, \cdots, n-1$.

Output: array $R[0], R[1], \cdots, R[n-1]$, which is a permutation of $0, 1, \cdots, n-1$ such that if $i<j$, then $R[P[i]] < R[P[j]]$.

Procedure: For $i$ in 0 to $n-1$ inclusive, let $R[P[i]]=i$.