Tutorialspoint.dev

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



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter