Reorder an Array According to the Given Indexes

Difficulty Level Easy
Frequently asked in Google
ArrayViews 2998

Problem Statement

Given an input array and the array of indexes, reorder an array according to the given indexes. Here we have to arrange the elements according to the indexes as per the given index array.

Example

Input : arr[] = [23,24,25] and given indexes are index[] = [1,0,2]

23 should be moved to Index 1. 24 should be moved to Index 0 and 25 should be at Index 2.

Output : arr[] = [24,23,25]

In the above example, the output array will have 23 in index 1, 24 in index 0, and 25 in index 2.

Approach 1

Till the end of the array, pick each element
while index[i] is not equal to i
a. swap the elements at arr[i] and arr[index[i]]
b. swap the indexes at index[i], index[index[i]]

Implementation  for Reorder an Array According to the Given Indexes

C++ Program

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int N;
  cin>>N;
  int arr[N];
  int index[N];
  for(int i=0;i<N;i++)
  {
      cin>>arr[i];
  }
  for(int i=0;i<N;i++)
  {
      cin>>index[i];
  }
  for(int i=0; i<N;i++)
  while(index[i] != i) //keep looping till index[i] is not equal to actual index
  {
     swap(arr[i],arr[index[i]]); //swap both the elements
     swap(index[i],index[index[i]]);  //swap both the indices
  }  
  for(int i=0;i<N;i++)
  cout<<arr[i] <<" ";
  return 0;
}

Java Program

import java.util.Scanner;
import java.util.Stack;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        int index[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        for(int i=0;i<n;i++)
        {
            index[i] = sr.nextInt();
        }
        for(int i=0; i<n;i++)
        {
            while(index[i] != i) //keep looping till index[i] is not equal to actual index
            {
                a[i]=a[i]+a[index[i]]-(a[index[i]]=a[i]);
                index[i]=index[i]+index[index[i]]-(index[index[i]]=index[i]);
            }
        }  
        for(int i=0;i<n;i++)
        {
            System.out.print(a[i]+" ");
        }
        System.out.println();
    }
}
6
13 53 12 7 3 1
0 5 3 2 4 1
13 1 7 12 3 53

Complexity Analysis for Reorder an Array According to the Given Indexes

Time Complexity

O(n) where n is the size of the given array. Here we swap the value of the array at any index using the index array. Here we swap at most n steps.

Auxiliary space

O(1) because we don’t use any auxiliary space here.

Approach 2

In this approach, we take an array and store the elements using the index array at the right position.

Algorithm

  1. Creating an auxiliary array to store the final result.
  2. Iterate while we reach at the end of the array.
    1. Place the elements in the auxiliary array, according to the index by going to that index
    ie, auxiliary array[index[i]]= arr[i]

Implementation for Reorder an Array According to the Given Indexes

C++ Program

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int N;
  cin>>N;
  int arr[N];
  int index[N];
  for(int i=0;i<N;i++)
  {
      cin>>arr[i];
  }
  for(int i=0;i<N;i++)
  {
      cin>>index[i];
  }
  int final[N];//create an auxiliary array to store the final result
  for(int i=0; i<N;i++)
    final[index[i]]  = arr[i]; //place the elements according to index by going to that index
    
  for(int i=0;i<N;i++)
    cout<<final[i] <<" ";
  return 0;
}

Java Program

import java.util.Scanner;
import java.util.Stack;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        int index[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        for(int i=0;i<n;i++)
        {
            index[i] = sr.nextInt();
        }
        int ans[] = new int [n];//create an auxiliary array to store the final result
        for(int i=0; i<n;i++)
          ans[index[i]]  = a[i]; //place the elements according to index by going to that index
        for(int i=0;i<n;i++)
        {
            System.out.print(ans[i]+" ");
        }
        System.out.println();
    }
}
3
23 24 25
1 0 2
24 23 25

Complexity Analysis

Time Complexity

O(n) where n is the size of the given array. Here we traverse the array from start to end and store the elements in the new array.

Auxiliary space

O(n) because we use another array to store the elements according to the index.

References

Translate »