In this article we are going to discuss an interview question that is asked quite frequently in companies like Facebook, Microsoft, or Google.

The problem statement goes as follows: Given an `vector<T> A`

of elements of type `T`

of length `N`

and a `vector<size_t> P`

where `P`

is a permutation of numbers from `[0-N-1]`

you need to apply the permutation `P`

to the vector A. You are not allowed to use more than `O(1)`

additional space.

For example suppose `A=['a','b','c','d']`

and `P=['2','0','4','1']`

. After applying `P`

to `A`

, the latter becomes: `['c','a','d','b']`

. `P[i]`

basically tell you which element of `A`

should go in position `i`

in the final arrangement of `A`

.

Solving this problem can be very easy if you are allowed to use additional `O(n)`

memory. All you need to do is to construct a new array, taking the elements as specified in `P`

. The following code shows how this approach can be implemented in `C++`

template<typename T> void apply_permutation(vector<T>& A, const vector<int>& P) { vector<T> A1; A1.reserve(A.size()); for(size_t i = 0 ; i < A.size() ; i++) A1.push_back(std::move(A[P[i]])); A = move(A1); }

Note how we use `move`

which will avoid the copy if possible) of potentially heavy objects. Once the additional array `A1`

has been constructed, we modify `A`

by moving `A1`

into it. That is pretty easy stuff.

In order to solve the hardest version we need to work a bit more.

The approach that will lead to the correct solution goes as follows: for each element that it is not yet in the correct location, then move it to its correct location. Sounds easy, and in-fact it it. Let's use the following concrete problem instance example as a guide:

- A = [a,b,c,d,e,f]
- P = [3,1,0,2,5,4]

For i = 0 we notice that `P[i] != 0`

, meaning that in `A[i]`

we should move`A[3]`

. In order to achieve so we `swap(A[i], A[3])`

which results in `A=[d, b, c, a, e, f]`

. Now the first position of the answer is correct. Well done.

But we moved element originally at position`i=0`

to position `3`

which is clearly not its correct position ( because according to `P, a`

should be placed in position `2)`

. What do we do? We swap the correct element ( `A[P[3]]`

) with `A[3]=a`

. In other words we substitute the `a`

with the element that should really go in that position i.e. `c`

. After `swap(A[3], A[2]), A=[d,b,a,c,e,f]. a`

is now not at location `2`

and `P[2]`

says that the element that should go here is `a.`

good, we found the correct spot for the element originally in position `i=0`

. In the process we also placed many other elements in the correct position.

Ideally now we should process another element that is not in its correct location. But how do we know which one is in the correct location? Since we cannot use any additional memory, we need to be clever and use `P`

instead. What if we set `P[i] = i`

whenever we do a swap? If we do that then we do not really do nothing for that element because when `P[i]= i`

there is no work to do, as the element is already in its final location.

If we apply this line of reasoning to all elements of `A`

then the final result will be what we really expected. Basically for an element `i`

not yet in its correct location we keep swapping it until it reaches its final location. If we do it for all elements, then by definition we have solved the problem.

I am sure the idea above will be much more clear once we look at the code: curr and next are respectively the indices of the elements we are considering for a swap.

template<typename T> void apply_permutation_in_place(vector<T>& A, vector<int>& P) { for(size_t i = 0 ; i < A.size() ; i++){ size_t curr = i; size_t next = P[curr]; while(next != i) { swap(A[curr], A[next]); P[curr] = curr; curr = next; next = P[next]; } P[curr] = curr; } }

You can try the above code online on wandbox ( https://wandbox.org/permlink/NevnhZFq2G0cgL7O ).

Be the first to leave a comment. Don’t be shy.