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

Java

Download   Run Code

 
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

Java

Download   Run Code

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

 
1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Allen
Guest

This algorithm seems incorrect? The example {4,0,3,1,2} does not have the desired property (as A[A[0]] = 2).

It suffices to replace A[i] by A[A[i]] which can be done by the following:

(1) A[i] += (A[A[i]%n)*n
(2) A[i] /= n