# Rearrange an array

Given an array of elements of length N, ranging from 0 to N – 1. All elements may not be present in the array. If the element is not present then there will be -1 present in the array. Rearrange the array such that A[i] = i and if i is not present, display -1 at that place.

Examples:

Input : arr = {-1, -1, 6, 1, 9, 3, 2, -1, 4, -1} Output : [-1, 1, 2, 3, 4, -1, 6, -1, -1, 9] Input : arr = {19, 7, 0, 3, 18, 15, 12, 6, 1, 8, 11, 10, 9, 5, 13, 16, 2, 14, 17, 4} Output : [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]

Approach(Naive Approach):

1. Nav­i­gate the numbers from 0 to n-1.
2. Now navigate through array.
3. If (i==a[j]) , then replace the element at i position with a[j] position.
4. If there is any element in which -1 is used instead of the number then it will be replaced automatically.
5. Now, iterate through the array and check if (a[i]!=i) , if it s true then replace a[i] with -1.

Below is the implementation for the above approach:

• C++

`// C++ program for above approach`

`#include <iostream>`

`using` `namespace` `std;`

`// Function to tranform the array`

`void` `fixArray(` `int` `ar[], ` `int` `n)`

`{`

`` `int` `i, j, temp;`

`` `// Iterate over the array`

`` `for` `(i = 0; i < n; i++)`

`` `{`

`` `for` `(j = 0; j < n; j++)`

`` `{`

`` `// Checf is any ar[j]`

`` `// exists such that`

`` `// ar[j] is equal to i`

`` `if` `(ar[j] == i) {`

`` `temp = ar[j];`

`` `ar[j] = ar[i];`

`` `ar[i] = temp;`

`` `break` `;`

`` `}`

`` `}`

`` `}`

`` `// Iterate over array`

`` `for` `(i = 0; i < n; i++)`

`` `{`

`` `// If not present`

`` `if` `(ar[i] != i)`

`` `{`

`` `ar[i] = -1;`

`` `}`

`` `}`

`` `// Print the output`

`` `cout << ` `"Array after Rearranging"` `<< endl;`

`` `for` `(i = 0; i < n; i++) {`

`` `cout << ar[i] << ` `" "` `;`

`` `}`

`}`

`// Driver Code`

`int` `main()`

`{`

`` `int` `n, ar[] = { -1, -1, 6, 1, 9, 3, 2, -1, 4, -1 };`

`` `n = ` `sizeof` `(ar) / ` `sizeof` `(ar);`

`` `// Function Call`

`` `fixArray(ar, n);`

`}`

Output

Array after Rearranging -1 1 2 3 4 -1 6 -1 -1 9

Time Complexity: O(n2)

Another Approach:

1. Nav­i­gate through the array.
2. Check if a[i] = -1, if yes then ignore it.
3. If a[i] != -1, Check if element a[i] is at its cor­rect posi­tion (i=A[i]) . If yes then ignore it.
4. If a[i] != -1 and ele­ment a[i] is not at its cor­rect posi­tion (i!=A[i]) then place it to its correct posi­tion, but there are two conditions:
• Either A[i] is vacate , means A[i] = -1 , then just put A[i] = i .
• OR A[i] is not vacate , means A[i] = x , then int y=x put A[i] = i . Now, we need to place y to its cor­rect place, so repeat from step 3.

Below is the implementation for the above approach:

• C++

`// C++ program for rearrange an`

`// array such that arr[i] = i.`

`#include <bits/stdc++.h>`

`using` `namespace` `std;`

`// Function to rearrange an array`

`// such that arr[i] = i.`

`void` `fixArray(` `int` `A[], ` `int` `len)`

`{`

`` `for` `(` `int` `i = 0; i < len; i++)`

`` `{`

`` `if` `(A[i] != -1 && A[i] != i)`

`` `{`

`` `int` `x = A[i];`

`` `// check if desired place`

`` `// is not vacate`

`` `while` `(A[x] != -1 && A[x] != x)`

`` `{`

`` `// store the value from`

`` `// desired place`

`` `int` `y = A[x];`

`` `// place the x to its correct`

`` `// position`

`` `A[x] = x;`

`` `// now y will become x, now`

`` `// search the place for x`

`` `x = y;`

`` `}`

`` `// place the x to its correct`

`` `// position`

`` `A[x] = x;`

`` `// check if while loop hasn't`

`` `// set the correct value at A[i]`

`` `if` `(A[i] != i)`

`` `{`

`` `// if not then put -1 at`

`` `// the vacated place`

`` `A[i] = -1;`

`` `}`

`` `}`

`` `}`

`}`

`// Driver code`

`int` `main()`

`{`

`` `int` `A[] = { -1, -1, 6, 1, 9,`

`` `3, 2, -1, 4, -1 };`

`` `int` `len = ` `sizeof` `(A) / ` `sizeof` `(A);`

`` `// Function Call`

`` `fixArray(A, len);`

`` `// Print the output`

`` `for` `(` `int` `i = 0; i < len; i++)`

`` `cout << A[i] << ` `" "` `;`

`}`

Output

-1 1 2 3 4 -1 6 -1 -1 9

Another Approach (Using HashSet) :

1. Store all the numbers present in the array into a HashSet
2. Iterate through the length of the array, if the corresponding position element is present in the HashSet, then set A[i] = i, else A[i] = -1

Below is the implementation of the above approach.

• C++

`#include <iostream>`

`#include <unordered_map>`

`using` `namespace` `std;`

`//`

`void` `fixArray(` `int` `arr[], ` `int` `n)`

`{`

`` `// Initialize a hashmap`

`` `std::unordered_map<` `int` `, ` `int` `> hmap;`

``

`` `// Enter each element in hmap`

`` `for` `(` `int` `i{0}; i<n; i++)`

`` `{`

`` `if` `(arr[i] != -1)`

`` `hmap[arr[i]] = 1;`

`` `}`

``

`` `// Navigate through array,`

`` `// and put A[i] = i,`

`` `// if i is present in hmap`

`` `for` `(` `int` `i{0}; i<n; i++)`

`` `{`

`` `// if i(index) is found in hmap`

`` `if` `(hmap.find(i) != hmap.end())`

`` `{`

`` `arr[i] = i;`

`` `}`

`` `// if i not found`

`` `else`

`` `{`

`` `arr[i] = -1;`

`` `}`

`` `}`

``

`}`

`// Driver Code`

`int` `main() {`

``

`` `// Array initialization`

`` `int` `arr[] {-1, -1, 6, 1, 9,`

`` `3, 2, -1, 4,-1};`

`` `int` `n = ` `sizeof` `(arr) / ` `sizeof` `(arr);`

``

`` `// Function Call`

`` `fixArray(arr, n);`

``

`` `// Print output`

`` `for` `(` `int` `i{0}; i<n; i++)`

`` `std::cout << arr[i] << ` `' '` `;`

``

`` `return` `0;`

`}`

Output

-1 1 2 3 4 -1 6 -1 -1 9

Another Approach (Swap elements in Array) :

1. Iterate through elements in an array
2. If arr[i] >= 0 && arr[i] != i, put arr[i] at i ( swap arr[i] with arr[arr[i]])

Below is the implementation of above approach.

• C++

`// C++ program for rearrange an`

`// array such that arr[i] = i.`

`#include <stdio.h>`

`void` `fixArray(` `int` `arr[], ` `int` `n)`

`{`

`` `for` `(` `int` `i = 0; i < n;)`

`` `{`

`` `if` `(arr[i] >= 0 && arr[i] != i)`

`` `arr[arr[i]] = (arr[arr[i]] + arr[i])`

`` `- (arr[i] = arr[arr[i]]);`

`` `else`

`` `i++;`

`` `}`

`}`

`// Driver Code`

`int` `main()`

`{`

`` `int` `arr[] = { -1, -1, 6, 1, 9, 3, 2, -1, 4, -1 };`

`` `int` `n = ` `sizeof` `(arr) / ` `sizeof` `(arr);`

`` `// Fucnction Call`

`` `fixArray(arr, n);`

`` `// Print output`

`` `for` `(` `int` `i = 0; i < n; i++)`

`` `printf` `(` `"%d "` `, arr[i]);`

`` `return` `0;`

`}`

Output

-1 1 2 3 4 -1 6 -1 -1 9

Time Complexity: O(n)