Rearrange array such that A[A[i]] is set to i for every element A[i]

Given an unsorted array of integers whose each element lies in range 0 to n-1 where n is the size of the array, rearrange array such that A[A[i]] is set to i for every element A[i] in the array.

Do this in linear time and without using any extra constant space.
 

For example,


Input:  {1, 3, 4, 2, 0}
Output: {4, 0, 3, 1, 2}

Explanation:
A[0] = 1, A[1] becomes 0
A[1] = 3, A[3] becomes 1
A[2] = 4, A[4] becomes 2
A[3] = 2, A[2] becomes 3
A[4] = 0, A[0] becomes 4

 


 

Simple solution would be to create an auxiliary array of size n and for each element A[i] of the input array, we set value i at index A[i] in the auxiliary array.

C

Download   Run Code

Output:

4 0 3 1 2

C++

Download   Run Code

Output:

4 0 3 1 2

Java

Download   Run Code

Output:

4 0 3 1 2

The time complexity of above solution is O(n) and auxiliary space used by the program is O(n).

 


 

Above solution uses extra space that violates the problem constraints. We can solve this problem without using any extra space by taking advantage of the fact that array elements lies in the range 0 to n-1. For each element A[i] present in the array, we increment value present at index (A[i] % n) by i*n. Finally, we traverse the modified array and set (A[i] = A[i]/n).

For example, consider array {1, 3, 4, 2, 0}. After incrementing value present at index (A[i] % n) for each element A[i] by i*n, the array becomes

{1 + 5*4, 3, 4 + 5*3, 2 + 5*1, 0 + 5*2} = {21, 3, 19, 7, 10}.

Now if we take (arr[i]/n) for each index i, we get {4, 0, 3, 1, 2}.

C

Download   Run Code

Output:

4 0 3 1 2

C++

Download   Run Code

Output:

4 0 3 1 2

Java

Download   Run Code

Output:

4 0 3 1 2

The time complexity of above solution is O(n) and auxiliary space used by the program is O(1).
 

Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂