Rearrange an array such that arr[i] = i

Read

Discuss(120)

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):

Navigate the numbers from 0 to n-1.
Now navigate through array.
If (i==a[j]) , then replace the element at i position with a[j] position.
If there is any element in which -1 is used instead of the number then it will be replaced automatically.
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 transform 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++)
        {
            // Check 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[0]);
 
    // Function Call
    fixArray(ar, n);
}
 
// Code BY Tanmay Anand

C

// C program for above approach
#include <stdio.h>
 
// Function to transform 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++)
        {
            // Check 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
    printf("Array after Rearranging\n");
    for (i = 0; i < n; i++) {
        printf("%d ",ar[i]);
    }
}
 
// Driver Code
int main()
{
    int n, ar[] = { -1, -1, 6, 1, 9, 3, 2, -1, 4, -1 };
    n = sizeof(ar) / sizeof(ar[0]);
 
    // Function Call
    fixArray(ar, n);
}
 
// This code is contributed by kothvvsaakash.

Java

// Java program for above approach
public class GFG{
     
// Function to transform the array
public static 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++)
        {
             
            // Check 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
    System.out.println("Array after Rearranging");
    for(i = 0; i < n; i++) 
    {
        System.out.print(ar[i] + " ");
    }
}
 
// Driver Code
public static void main(String[] args)
{
    int n, ar[] = { -1, -1, 6, 1, 9, 
                     3, 2, -1, 4, -1 };
    n = ar.length;
  
    // Function Call
    fixArray(ar, n);
}
}
 
// This code is contributed by divyesh072019

Python3

# Python3 program for above approach
 
# Function to transform the array
def fixArray(ar, n):
     
    # Iterate over the array
    for i in range(n):
        for j in range(n):
 
            # Check is any ar[j]
            # exists such that
            # ar[j] is equal to i
            if (ar[j] == i):
                ar[j], ar[i] = ar[i], ar[j]
 
    # Iterate over array
    for i in range(n):
         
        # If not present
        if (ar[i] != i):
            ar[i] = -1
 
    # Print the output
    print("Array after Rearranging")
 
    for i in range(n):
        print(ar[i], end = " ")
 
# Driver Code
ar = [ -1, -1, 6, 1, 9, 3, 2, -1, 4, -1 ]
n = len(ar)
 
# Function Call
fixArray(ar, n);
 
# This code is contributed by rag2127

C#

// C# program for above approach
using System;
class GFG {
     
    // Function to transform the array
    static 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++)
            {
                  
                // Check 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
        Console.WriteLine("Array after Rearranging");
        for(i = 0; i < n; i++) 
        {
            Console.Write(ar[i] + " ");
        }
    }  
     
  static void Main() {
        int[] ar = { -1, -1, 6, 1, 9, 
                     3, 2, -1, 4, -1 };
        int n = ar.Length;
       
        // Function Call
        fixArray(ar, n);
  }
}
 
// This code is contributed by divyeshrabadiya07

Javascript

<script>
      // JavaScript program for above approach
 
      // Function to transform the array
      function fixArray(ar, n) {
        var i, j, temp;
 
        // Iterate over the array
        for (i = 0; i < n; i++) 
        {
          for (j = 0; j < n; j++) 
          {
           
            // Check 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
        document.write("Array after Rearranging");
        document.write("<br>");
        for (i = 0; i < n; i++) {
          document.write(ar[i] + " ");
        }
      }
 
      // Driver Code
 
      var n,
      ar = [-1, -1, 6, 1, 9, 3, 2, -1, 4, -1];
      n = ar.length;
 
      // Function Call
      fixArray(ar, n);
 
      // This code is contributed BY Rahul Tank
    </script>

Output

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

Time Complexity: O(n²)
Auxiliary Space: O(1), since no extra space has been taken.

Another Approach:
1. Navigate 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 correct position (i=A[i]). If yes then ignore it.
4. If a[i] != -1 and element a[i] is not at its correct position (i!=A[i]) then place it to its correct position, 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 correct 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[0]);
 
    // Function Call
    fixArray(A, len);
 
    // Print the output
    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 code
    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)));
    }
}

C

// C program for rearrange an
// array such that arr[i] = i.
#include <stdio.h>
 
// 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[0]);
 
    // Function Call
    fixArray(A, len);
 
    // Print the output
    for (int i = 0; i < len; i++)
        printf("%d ",A[i]);
}
 
// This code is contributed by kothavvsaakash

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 code
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

<?php
// PHP program for rearrange an
// array such that arr[i] = i.
 
// Function to rearrange an 
// array such that arr[i] = i.
function fix(&$A, $len)
{
    for ($i = 0; $i < $len; $i++) 
    {
        if ($A[$i] != -1 && 
            $A[$i] != $i) 
        {
            $x = $A[$i];
 
            // check if desired 
            // place is not vacate
            while ($A[$x] != -1 && 
                   $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 Code
$A = array(-1, -1, 6, 1, 9,
            3, 2, -1, 4, -1);
 
$len = count($A);
fix($A, $len);
 
for ($i = 0; $i < $len; $i++)
    echo ($A[$i]." ");
     
// This code is contributed by 
// Manish Shaw(manishshaw1)
?>

Javascript

<script>
// Javascript program for rearrange an
// array such that arr[i] = i.
 
// Function to rearrange an 
// array such that arr[i] = i.
function fix(A, len)
{
    for (let i = 0; i < len; i++) 
    {
        if (A[i] != -1 && 
            A[i] != i) 
        {
            let x = A[i];
 
            // check if desired 
            // place is not vacate
            while (A[x] != -1 && 
                   A[x] != x)
            {
                // store the value 
                // from desired place
                let 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
let A = new Array(-1, -1, 6, 1, 9,
            3, 2, -1, 4, -1);
 
let len = A.length;
fix(A, len);
 
for (let i = 0; i < len; i++)
    document.write(A[i] + " ");
     
// This code is contributed by gfgking
</script>

Output

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

Time Complexity: O(n)
Auxiliary Space: O(1)

Another Approach (Using Set) :
1) Store all the numbers present in the array into a Set
2) Iterate through the length of the array, if the corresponding position element is present in the Set, then set A[i] = i, else A[i] = -1

Below is the implementation of the above approach.

C++

#include <iostream>
#include <unordered_set>
 
using namespace std;
 
void fixArray(int arr[], int n)
{
  // a set
  unordered_set<int> s;
   
  // Enter each element which is not -1 in set
  for(int i=0; i<n; i++)
  {
    if(arr[i] != -1)
      s.insert(arr[i]);
  }
   
  // Navigate through array,
  // and put A[i] = i,
  // if i is present in set
  for(int i=0; i<n; i++)
  {
    // if i(index) is found in hmap
    if(s.find(i) != s.end())
    {
      arr[i] = i;
    }
    // if i is 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[0]);
   
  // Function Call
  fixArray(arr, n);
   
  // Print output
  for(int i=0; i<n; i++)
    cout << arr[i] << ' ';
   
  return 0;
}
 
// this code is contributed by dev chaudhary

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<Integer> s = new HashSet<Integer>();
 
        // 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 code
    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

# Python3 program 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))
 
# This code is contributed by Chitranayal

C#

using System;
using System.Collections.Generic;
public class main{
    static void fix(int[] a,int n){
       HashSet<int> hs=new HashSet<int>();
         
        // Traverse the array
        // and add each element
        // to the HashSet
        for(int i=0;i<n;i++)
        hs.Add(a[i]);
         
        // Again traverse from i=0 -> i=n-1
        for(int i=0;i<n;i++)
        {
            // If HashSet contains i
            // Then make a[i]=i,
            // else a[i]=-1
            if(hs.Contains(i))
            a[i]=i;
            else
            a[i]=-1;
        }
    }
    static public void Main (){
        int[] arr={-1, -1, 6, 1, 9, 
                             3, 2, -1, 4,-1};
        int n=arr.Length;
        fix(arr,n);
         
        for(int i=0;i<n;i++) 
        Console.Write(arr[i]+" ");
         
        Console.WriteLine();
    }
}

Javascript

<script>
 
    // JavaScript program for rearrange an
    // array such that arr[i] = i.
     
    // Function to rearrange an array
    // such that arr[i] = i.
    function fix(A)
    {
        let s = new Set();
  
        // Storing all the values in the HashSet
        for(let i = 0; i < A.length; i++)
        {
           s.add(A[i]);
        }
  
        for(let i = 0; i < A.length; i++)
        {
           if(s.has(i))
             A[i] = i;
           else
             A[i] = -1;
        }
  
          return A;
    }
     
    let A = [-1, -1, 6, 1, 9, 3, 2, -1, 4,-1];
                      
    // Function calling
    let ans = fix(A);
    for(let i = 0; i < ans.length; i++)
    {
        document.write(ans[i] + " ");
    }
 
</script>

Output

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

Time Complexity: O(n²)
Auxiliary Space: O(n)

Another Approach (Swap elements in Array) : Using cyclic sort
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 the above approach.

C++

// C++ program for rearrange an
// array such that arr[i] = i.
#include <iostream>
using namespace std;
 
void fixArray(int arr[], int n)
{
 
    int i = 0;
    while (i < n) {
        int correct = arr[i];
        if (arr[i] != -1 && arr[i] != arr[correct]) {
          // if array element should be lesser than
          // size and array element should not be at
          // its correct position then only swap with
          // its correct position or index value
            swap(arr[i], arr[correct]);
        }
        else {
          // if element is at its correct position
          // just increment i and check for remaining
          // array elements
            i++;
        }
    }
    return arr;
}
 
// Driver Code
int main()
{
    int arr[] = { -1, -1, 6, 1, 9, 3, 2, -1, 4, -1 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    fixArray(arr, n);
 
    // Print output
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    return 0;
}
 
// This Code is Contributed by kothavvsaakash

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[0]);
 
    // Function Call
    fixArray(arr, n);
 
    // Print output
    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*/

Python3

# Python3 program for rearrange an
# array such that arr[i] = i.
if __name__ == "__main__":
 
    arr = [-1, -1, 6, 1, 9,
           3, 2, -1, 4, -1]
    n = len(arr)
    i = 0
    while i < n:
 
        if (arr[i] >= 0 and arr[i] != i):
            (arr[arr[i]],
             arr[i]) = (arr[i],
                        arr[arr[i]])
        else:
            i += 1
 
    for i in range(n):
        print(arr[i], end=" ")
 
# This code is contributed by Chitranayal

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 < arr.Length;)
        {
            if (arr[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)

Javascript

<script>
// Javascript program for rearrange an
// array such that arr[i] = i.
 
function fixArray(arr, n)
{
 
    for (let 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
 
    let arr = [ -1, -1, 6, 1, 9, 3, 2, -1, 4, -1 ];
    let n = arr.length;
 
    // Function Call
    fixArray(arr, n);
 
    // Print output
    for (let i = 0; i < n; i++)
        document.write(arr[i] + " ");
     
 
// This Code is Contributed by _saurabh_jaiswal
</script>

Output

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

Time Complexity: O(n)
Auxiliary Space: O(1)

Another Approach (Using Vector) :

Follow these steps to rearrange an array

Make a vector of size n and fill its every element by -1.
Now traverse the input array and if any element is not equal to -1 then
- Fill that index of the vector which is equal to the element of the input array by that element’s value
In last copy all elements of the vector into the input array and then return or print that input array

Code-

C++

// C++ program for rearrange an
// array such that arr[i] = i.
#include <bits/stdc++.h>
using namespace std;
 
int* fixArray(int arr[], int n)
{
    vector<int> vec(n, -1);
    for (int i = 0; i < n; i++) {
        if (arr[i] != -1) {
            vec[arr[i]] = arr[i];
        }
    }
 
    for (int i = 0; i < n; i++) {
        arr[i] = vec[i];
    }
    return arr;
}
 
// Driver Code
int main()
{
    int arr[] = { -1, -1, 6, 1, 9, 3, 2, -1, 4, -1 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    fixArray(arr, n);
 
    // Print output
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    return 0;
}

Java

import java.util.*;
 
public class Main {
    static int[] fixArray(int arr[], int n)
    {
        ArrayList<Integer> vec
            = new ArrayList<>(Collections.nCopies(n, -1));
        for (int i = 0; i < n; i++) {
            if (arr[i] != -1) {
                vec.set(arr[i], arr[i]);
            }
        }
 
        for (int i = 0; i < n; i++) {
            arr[i] = vec.get(i);
        }
        return arr;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int arr[] = { -1, -1, 6, 1, 9, 3, 2, -1, 4, -1 };
        int n = arr.length;
 
        // Function Call
        fixArray(arr, n);
 
        // Print output
        for (int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");
    }
}

Python3

# Python program for rearranging
# an array such that arr[i] = i.
   
def fixArray(arr, n):
    vec = [-1]*n
   
    # Traverse the array
    for i in range(0, n):
   
        # If arr[i] is not -1 then arr[i]
        # is at its correct position.
        if (arr[i] != -1):
            vec[arr[i]] = arr[i]
   
    # Copy vec[] to arr[]
    for i in range(0, n):
        arr[i] = vec[i]
    return arr
   
# Driver code
arr = [-1, -1, 6, 1, 9, 3, 2, -1, 4, -1]
n = len(arr)
   
# Function call
fixArray(arr, n)
   
# Print output
for i in range(0, n):
    print(arr[i], end=" ")

C#

// C# code addition 
using System;
class GFG
{
   
    // Function to rearrange an
    // array such that arr[i] = i.
    static int[] FixArray(int[] arr, int n)
    {
        var vec = new int[n];
        for (int i = 0; i < n; i++) {
            vec[i] = -1;
        }
 
        for (int i = 0; i < n; i++) {
            if (arr[i] != -1) {
                vec[arr[i]] = arr[i];
            }
        }
 
        for (int i = 0; i < n; i++) {
            arr[i] = vec[i];
        }
        return arr;
    }
 
    // Driver Code
    public static void Main(string[] args)
    {
        int[] arr = { -1, -1, 6, 1, 9, 3, 2, -1, 4, -1 };
        int n = arr.Length;
 
        // Function Call
        FixArray(arr, n);
 
        // Print output
        for (int i = 0; i < n; i++)
            Console.Write(arr[i] + " ");
    }
}
 
// The code is contributed by Arushi Goel.

Javascript

// JavaScript program for rearrange an
// array such that arr[i] = i.
 
function fixArray(arr) {
    let n = arr.length;
    let vec = new Array(n).fill(-1);
     
    for (let i = 0; i < n; i++) {
        if (arr[i] !== -1) {
            vec[arr[i]] = arr[i];
        }
    }
     
    for (let i = 0; i < n; i++) {
        arr[i] = vec[i];
    }
     
    return arr;
}
 
// Driver Code
let arr = [-1, -1, 6, 1, 9, 3, 2, -1, 4, -1];
 
// Function Call
fixArray(arr);
 
// Print output
console.log(arr.join(" "));

Output-

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

Time Complexity: O(n)
Auxiliary Space: O(n),for vector

Feeling lost in the world of random DSA topics, wasting time without progress? It's time for a change! Join our DSA course, where we'll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 geeks!

Last Updated : 11 Apr, 2023