# Given permutation $p$, compute $p^{-2}$

I'm now to problem solving, and I need some help and insight on the following problem from HackerRank:

Given a sequence $$p(1),\ldots,p(n)$$ of distinct numbers from $$1$$ to $$n$$, find numbers $$y_1,\ldots,y_n$$ such that $$p(p(y_1))=1,\ldots,p(p(y_n))=n$$.

My approach was to perform a double index lookup on each element in the provided input: for each $$i \in \{1,\ldots,n\}$$, I find an index $$z_i$$ such that $$p(z_i) = i$$, and then an index $$y_i$$ such that $$p(y_i) = i$$.

Is there a more efficient way to solve this problem?

• Can you compute a reverse permutation for $p$ in $O(n)$ time? Commented Nov 7, 2020 at 2:00
• Please make sure you include the statement of the problem in your question, so it is self-contained.
– D.W.
Commented Nov 7, 2020 at 2:22
• @VladislavBezhentsev to be honest I didn't even understand the question and just figured out what it meant after some trial and error while mapping the input to the output. Commented Nov 7, 2020 at 5:39

The first step in answering your question is determining the complexity of your algorithm. Determining the index $$z_i$$ takes time $$\Theta(z_i)$$, and so determining all of $$z_1,\ldots,z_n$$ takes time $$\Theta(1+\cdots+n) = \Theta(n^2)$$. Determining the $$y_i$$ from the $$z_i$$ likewise takes $$\Theta(n^2)$$, which is the running time of your algorithm.
If we are willing to spend memory $$O(n)$$, then we can improve the running time to $$O(n)$$. The idea is to notice that $$p$$ is a permutation, and therefore has an inverse $$p^{-1}$$, which can be computed easily as follows: go over $$i=1,\ldots,n$$, and set $$p^{-1}(p(i))=i$$. Given that, we can simply compute $$z_i = p^{-1}(p^{-1}(i))$$.
If you are really short on memory, there are algorithms for inverting a permutation in nearly linear time and small space, see for example Matthew Robertson, Inverting permutations in place. After inverting $$p$$, you need to square the result $$p^{-1}$$, which might be achievable using similar techniques (or even easier).
• The numbers $p(1),\ldots,p(n)$ form a permutation of $1,\ldots,n$. Finding the inverse permutation is extremely easy – I gave the algorithm in my answer. Read it carefully. Commented Nov 7, 2020 at 10:36