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

Question

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?

Answer 1

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