# 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
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 26, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "https://cs.stackexchange.com/questions/132001/given-permutation-p-compute-p-2", "fetch_time": 1723278103000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2024-33/segments/1722640790444.57/warc/CC-MAIN-20240810061945-20240810091945-00842.warc.gz", "warc_record_offset": 155796813, "warc_record_length": 41050, "token_count": 645, "char_count": 2260, "score": 3.828125, "int_score": 4, "crawl": "CC-MAIN-2024-33", "snapshot_type": "latest", "language": "en", "language_score": 0.8880280256271362, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00034-of-00064.parquet"}