# Rearrange an array such that arr[i] = i

Given an array of elements of length N, ranging from 0 to N – 1. All elements may not be present in the array. If 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:
1. Nav­i­gate 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 above approach:

## C++

 `// CPP program for rearrange an ` `// array such that arr[i] = i. ` `#include ` ` `  `using` `namespace` `std; ` ` `  `// Function to rearrange an array ` `// such that arr[i] = i. ` `int` `fix(``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 function. ` `int` `main() ` `{ ` `    ``int` `A[] = { -1, -1, 6, 1, 9, ` `                ``3, 2, -1, 4, -1 }; ` ` `  `    ``int` `len = ``sizeof``(A) / ``sizeof``(A); ` `    ``fix(A, len); ` ` `  `    ``for` `(``int` `i = 0; i < len; i++) ` `        ``cout << A[i] << ``" "``; ` `} ` ` `  `// This code is contributed by Smitha Dinesh Semwal `

## Java

 `// Java program for rearrange an  ` `// array such that arr[i] = i. ` `import` `java.util.*; ` `import` `java.lang.*; ` ` `  `public` `class` `GfG { ` ` `  `    ``// Function to rearrange an array ` `    ``// such that arr[i] = i. ` `    ``public` `static` `int``[] fix(``int``[] A) ` `    ``{ ` `        ``for` `(``int` `i = ``0``; i < A.length; 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``; ` `                ``} ` `            ``} ` `        ``} ` `        ``return` `A; ` `    ``} ` ` `  `    ``// Driver function. ` `    ``public` `static` `void` `main(String[] args) ` `    ``{ ` `        ``int` `A[] = {-``1``, -``1``, ``6``, ``1``,  ` `                    ``9``, ``3``, ``2``, -``1``, ``4``,-``1``}; ` `        ``System.out.println(Arrays.toString(fix(A))); ` `    ``} ` `} `

## Python3

 `# Python3 program for rearrange an ` `# array such that arr[i] = i. ` ` `  `# Function to rearrange an array ` `# such that arr[i] = i. ` `def` `fix( A, ``len``): ` `     `  `    ``for` `i ``in` `range``(``0``, ``len``):  ` `         `  `        ``if` `(A[i] !``=` `-``1` `and` `A[i] !``=` `i): ` `            ``x ``=` `A[i]; ` ` `  `            ``# check if desired place ` `            ``# is not vacate ` `            ``while` `(A[x] !``=` `-``1` `and` `A[x] !``=` `x): ` `                ``#store the value from ` `                ``# desired place ` `                ``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 function. ` `A ``=` `[ ``-``1``, ``-``1``, ``6``, ``1``, ``9``, ``3``, ``2``, ``-``1``, ``4``, ``-``1` `] ` ` `  `fix(A, ``len``(A)) ` ` `  `for` `i ``in` `range``(``0``, ``len``(A)): ` `    ``print` `(A[i],end ``=` `' '``) ` `     `  `# This code is contributed by Saloni1297     `

## C#

 `// C# program for rearrange  ` `// an array such that  ` `// arr[i] = i. ` `using` `System; ` ` `  `class` `GfG  ` `{ ` `// Function to rearrange an  ` `// array such that arr[i] = i. ` `public` `static` `int``[] fix(``int``[] A) ` `{ ` `    ``for` `(``int` `i = 0;  ` `             ``i < A.Length; 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; ` `            ``} ` `        ``} ` `    ``} ` `    ``return` `A; ` `} ` ` `  `// Driver Code ` `static` `void` `Main() ` `{ ` `    ``int` `[]A = ``new` `int``[]{-1, -1, 6, 1, 9,  ` `                         ``3, 2, -1, 4,-1}; ` `    ``Console.WriteLine(``string``.Join(``","``, ` `                                 ``fix(A))); ` `} ` `} ` ` `  `// This code is contributed by  ` `// Manish Shaw(manishshaw1) `

## PHP

 ` `

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 above approach.

## Java

 `// Java program for rearrange an  ` `// array such that arr[i] = i. ` `import` `java.util.*; ` `import` `java.lang.*; ` ` `  `class` `GfG { ` ` `  `    ``// Function to rearrange an array ` `    ``// such that arr[i] = i. ` `    ``public` `static` `int``[] fix(``int``[] A) ` `    ``{ ` `        ``Set s = ``new` `HashSet(); ` ` `  `        ``// Storing all the values in the HashSet ` `        ``for``(``int` `i = ``0``; i < A.length; i++) ` `        ``{ ` `           ``s.add(A[i]); ` `        ``} ` ` `  `        ``for``(``int` `i = ``0``; i < A.length; i++) ` `        ``{ ` `           ``if``(s.contains(i)) ` `             ``A[i] = i; ` `           ``else` `             ``A[i] = -``1``; ` `        ``} ` ` `  `      ``return` `A; ` `} ` ` `  `    ``// Driver function. ` `    ``public` `static` `void` `main(String[] args) ` `    ``{ ` `        ``int` `A[] = {-``1``, -``1``, ``6``, ``1``, ``9``, ` `                    ``3``, ``2``, -``1``, ``4``,-``1``}; ` `                     `  `        ``// Function calling ` `        ``System.out.println(Arrays.toString(fix(A))); ` `    ``} ` `} `

## Python3

 `# Python3program for rearrange an  ` `# array such that arr[i] = i. ` ` `  ` `  `# Function to rearrange an array ` `# such that arr[i] = i. ` `def` `fix(A): ` `    ``s ``=` `set``() ` `     `  `    ``# Storing all the values in the Set ` `    ``for` `i ``in` `range``(``len``(A)): ` `        ``s.add(A[i]) ` ` `  `    ``for` `i ``in` `range``(``len``(A)): ` `        ``# check for item if present in set ` `        ``if` `i ``in` `s: ` `            ``A[i] ``=` `i ` `        ``else``: ` `            ``A[i] ``=` `-``1` `    ``return` `A ` `     `  `# Driver code ` `if` `__name__ ``=``=` `"__main__"``: ` `    ``A ``=` `[``-``1``, ``-``1``, ``6``, ``1``, ``9``, ` `        ``3``, ``2``, ``-``1``, ``4``,``-``1``] ` `    ``print``(fix(A)) `

## C#

 `// C# program for rearrange an  ` `// array such that arr[i] = i. ` `using` `System; ` ` `  `class` `GfG ` `{ ` ` `  `    ``// Function to rearrange  ` `    ``// an array such that ` `    ``// arr[i] = i. ` `    ``static` `int``[] fix(``int` `[]A) ` `    ``{ ` `        ``for` `(``int` `i = 0;  ` `                 ``i < A.Length; 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; ` `                ``} ` `            ``} ` `        ``} ` `        ``return` `A; ` `    ``}  ` `     `  `    ``// Driver Code ` `    ``static` `void` `Main() ` `    ``{ ` `        ``int` `[]A = ``new` `int``[]{-1, -1, 6, 1, 9,  ` `                             ``3, 2, -1, 4,-1}; ` `        ``Console.Write(``string``.Join(``","``, fix(A))); ` `    ``} ` `} ` ` `  `// This code is contributed by  ` `// Manish Shaw(manishshaw1) `

Output :

```[-1, 1, 2, 3, 4, -1, 6, -1, -1, 9]
```

Another Approach (Swap elements in Array) :
1) Iterate through elements in 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 ` ` `  `int` `main()  ` `{ ` `    ``int` `arr[] = {-1, -1, 6, 1, 9, 3, 2, -1, 4, -1}; ` `    ``int` `n = ``sizeof``(arr)/``sizeof``(arr); ` `    ``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++; ` `    ``} ` `    ``for``(``int` `i = 0; i < n; i++) ` `        ``printf``(``"%d "``,arr[i]); ` `        ``return` `0; ` `} ` ` `  `// This Code is Contributed by Adarsh_Verma  `

## Java

 `// Java program for rearrange an  ` `// array such that arr[i] = i. ` `import` `java.util.Arrays; ` ` `  `class` `Program { ` ` `  `    ``public` `static` `void` `main(String[] args) { ` `        ``int``[] arr = {-``1``, -``1``, ``6``, ``1``, ``9``, ``3``, ``2``, -``1``, ``4``, -``1``}; ` `        ``for` `(``int` `i = ``0``; i < arr.length;) { ` `            ``if` `(arr[i] >= ``0` `&& arr[i] != i) { ` `                ``int` `ele = arr[arr[i]]; ` `                ``arr[arr[i]] = arr[i]; ` `                ``arr[i] = ele; ` `            ``} ``else` `{ ` `                ``i++; ` `            ``} ` `        ``} ` `        ``System.out.println(Arrays.toString(arr)); ` `    ``} ` `} ` ` `  `  `  `/* This Java code is contributed by PrinciRaj1992*/`

## C#

 `// C# program for rearrange an  ` `// array such that arr[i] = i. ` `using` `System; ` ` `  `namespace` `GFG ` `{ ` `    ``class` `Program ` `    ``{ ` `        ``static` `void` `Main(``string``[] args) ` `        ``{ ` `            ``int``[] arr = {-1, -1, 6, 1, 9, 3, 2, -1, 4, -1}; ` `            ``for``(``int` `i = 0; i = 0 && arr[i] != i) ` `                ``{ ` `                    ``int` `ele = arr[arr[i]]; ` `                    ``arr[arr[i]] = arr[i]; ` `                    ``arr[i] = ele; ` `                ``} ``else` `{ ` `                    ``i++; ` `                ``} ` `            ``} ` `            ``Console.WriteLine(String.Join(``","``, arr)); ` `        ``} ` `    ``} ` `} ` `// This code is contributed by  ` `// Venkata VardhiReddy(venkata) `

Output :

```[-1, 1, 2, 3, 4, -1, 6, -1, -1, 9]
```

Time Complexity: O(n)

This article is attributed to GeeksforGeeks.org

## tags:

Arrays Hash array-rearrange Arrays Hash

code

load comments