less than 1 minute read

Apply Permutation to Array - Elements of Programming Interviews (EPI)

Problem:

Given an array A of \(n\) elements and a permutation P, apply P to A. For example if A = [a,b,c,d] and P = [2,0,1,3], then the result of applying P to A is [c,a,b,d] because P[i] represents the location in the result of the element i in A.

Solution:

The naive solution would be to make a new result array and iterate over P and put the corresponding element from A into the result array. This requires O(n) extra space. We can improve on this by taking advantage of the fact that the overall permutation can be divided into smaller cyclic permutations and those permutations can be done one operation at a time by swapping elements in A around.