1
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ Can you compute a reverse permutation for $p$ in $O(n)$ time? $\endgroup$ – Vladislav Bezhentsev Nov 7 '20 at 2:00
  • 1
    $\begingroup$ Please make sure you include the statement of the problem in your question, so it is self-contained. $\endgroup$ – D.W. Nov 7 '20 at 2:22
  • $\begingroup$ @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. $\endgroup$ – Harsha Limaye Nov 7 '20 at 5:39
2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ How can I make it run in linear time if I am willing to spend extra space ? Could you use the particular example to explain ? I'm afraid I do not understand much of the theory. I do not see what any of this has to do with a permutation(as I am not rearranging anything).. $\endgroup$ – Harsha Limaye Nov 7 '20 at 10:20
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Nov 7 '20 at 10:36

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.