# 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.

## Java

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}.

## Java

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

(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

Subscribe
Notify of
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