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

C++

// CPP 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. 
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[0]); 
    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

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

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<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 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<stdio.h> 
  
int main()  
{ 
    int arr[] = {-1, -1, 6, 1, 9, 3, 2, -1, 4, -1}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    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 <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) 

Output :

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

Time Complexity: O(n)

Rearrange an array such that arr[i] = i

C++

Java

Python3

C#

PHP

Java

Python3

C#

C++

Java

C#

tags:

leave a comment

0 Comments

Subscribe to Our Newsletter

Top Followed books