Rearrange array such that `A[A[i]]` is set to `i` for every element `A[i]`
Given an unsorted integer array A of size n, whose elements lie in the range 0 to n-1, rearrange the array such that A[A[i]] is set to i for every array element A[i]. Do this in linear time and without using any extra constant space.
For example,
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
A simple solution is to create an auxiliary array of size n, and for each element A[i] of the input array, set a value i at index A[i] in the auxiliary array. This approach is demonstrated below in C, Java, and Python:
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
#include <stdio.h> // Function to rearrange an array such that `A[A[i]]` is set to `i` // for every element `A[i]` void rearrange(int A[], int n) { // create an auxiliary array of size `n` int aux[n]; // for each element `A[i]` of the input array, set // value `i` at index `A[i]` in the auxiliary array for (int i = 0; i < n; i++) { aux[A[i]] = i; } // copy auxiliary array elements back to the given array for (int i = 0; i < n; i++) { A[i] = aux[i]; } } int main() { int A[] = { 1, 3, 4, 2, 0 }; int n = sizeof(A) / sizeof(A[0]); rearrange(A, n); for (int i = 0; i < n; i++) { printf("%d ", A[i]); } return 0; } |
Output:
[4, 0, 3, 1, 2]
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
import java.util.Arrays; class Main { public static void rearrange(int[] A) { // create an auxiliary array of the same size as `A[]` int[] aux = new int[A.length]; // for each element `A[i]`, set value `i` at index `A[i]` // in the auxiliary array for (int i = 0; i < A.length; i++) { aux[A[i]] = i; } // update original array with auxiliary array elements for (int i = 0; i < A.length; i++) { A[i] = aux[i]; } } public static void main (String[] args) { int[] A = { 1, 3, 4, 2, 0 }; rearrange(A); System.out.println(Arrays.toString(A)); } } |
Output:
[4, 0, 3, 1, 2]
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
def rearrange(A): # create an auxiliary array of the same size as `A[]` aux = [None] * len(A) # for each element `A[i]`, set value `i` at index `A[i]` # in the auxiliary array for i in range(len(A)): aux[A[i]] = i # update original array with auxiliary array elements for i in range(len(A)): A[i] = aux[i] print(A) if __name__ == '__main__': A = [1, 3, 4, 2, 0] rearrange(A) |
Output:
[4, 0, 3, 1, 2]
The time complexity of the above solution is O(n) and requires O(n) extra space, where n is the size of the input.
The 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 lie in range 0 to n-1. For each element A[i] present in the array, increment value present at index A[i] % n by i × n. Finally, 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 A[i] / n for each index i, we get {4, 0, 3, 1, 2}. Following is the C, Java, and Python implementation based on this idea:
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
#include <stdio.h> // Function to rearrange an array such that `A[A[i]]` is set to `i` // for every element `A[i]` void rearrange(int A[], int n) { // for each element `A[i]`, increment value present at index // `(A[i] % n)` by `i×n` for (int i = 0; i < n; i++) { A[A[i] % n] += i*n; } // traverse the modified array and set `A[i] = A[i]/n` for (int i = 0; i < n; i++) { A[i] = A[i] / n; } } int main() { int A[] = { 1, 3, 4, 2, 0 }; int n = sizeof(A) / sizeof(A[0]); rearrange(A, n); for (int i = 0; i < n; i++) { printf("%d ", A[i]); } return 0; } |
Output:
[4, 0, 3, 1, 2]
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
import java.util.Arrays; class Main { // Function to rearrange an array such that `A[A[i]]` is set to `i` // for every element `A[i]` public static void rearrange(int[] A) { int n = A.length; // for each element `A[i]`, increment value present at index // `(A[i] % n)` by `i×n` for (int i = 0; i < n; i++) { A[A[i] % n] += i*n; } // traverse the modified array and set `A[i] = A[i]/n` for (int i = 0; i < n; i++) { A[i] = A[i] / n; } } public static void main (String[] args) { int[] A = { 1, 3, 4, 2, 0 }; rearrange(A); System.out.println(Arrays.toString(A)); } } |
Output:
[4, 0, 3, 1, 2]
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
# Function to rearrange a list such that `A[A[i]` is set to `i` # for every element `A[i]` def rearrange(A): n = len(A) # for each element `A[i]`, increment value present at index # `(A[i] % n)` by `i×n` for i in range(n): A[A[i] % n] += i * n # traverse the modified list and set `A[i] = A[i] / n` for i in range(n): A[i] = A[i] // n if __name__ == '__main__': A = [1, 3, 4, 2, 0] rearrange(A) print(A) |
Output:
[4, 0, 3, 1, 2]
The time complexity of the above solution is O(n) and doesn’t require any extra space.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)