# Copying items in arrays while checking their indexes

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

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?

• "Value $x$ in array $P$ is on a lower index than value $y$ in array $P$". Does it mean "the index of value $x$ in array $P$ is smaller than the index of value $y$ in array $P$"? – Apass.Jack May 19 at 12:17
• Have you tried to find which element of $R$ should be mapped to 0? Then which element of $R$ should be mapped to 1? 2? And so on. – Apass.Jack May 19 at 12:25
• @Apass.Jack Well, it's exactly how I translated it. – james F. May 19 at 13:09

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). Then $$R[p_i] = i$$ and $$R[p_j] = j$$, and it holds that $$R[p_i]

You should be able to take it from here.

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, then $$R[P[i]] < R[P[j]]$$.

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