# Reorder Array Using Given Indexes

Difficulty Level Easy
ArrayViews 532

## Problem Statement

In recorder array using given indexes problem we have given two input arrays of the same size, the second array is index array, we need to reorder elements in the same array according to given index array.

## Example

Input
array : [4, 2, 1, 3]
index : [3, 1, 0, 2]

Output
array : [1, 2, 3, 4]
index : [0, 1, 2, 3]
Here, given index array is [3, 1, 0, 2],
Therefore, array[3] = 4, array[1] = 2, array[0] = 1, array[2] = 3.
Output will be: [1, 2, 3, 4]

Input
array : [9, 5, 3, 7, 11, 1]
index : [4, 2, 1, 0, 3, 5]

Output
array : [7, 3, 5, 11, 8, 9, 1]
index : [0, 1, 2, 3, 4, 5]

## Approach 1

### Algorithm

Step 1: Create a function that takes the two input arrays array[] and index[] and reorders based on index array.

Step 2: In the function,

a)    Create an auxiliary array temp same size of given arrays.
b)    Traverse the given array and put elements at their correct position in temp based on the index[]. temp[index[i]] = array[i]
c)    Copy this temp array as a given array and change index array based on indexes.

Step 3: call this function on given input arrays and print the arrays.

### Implementation

#### C++ Program for Reorder Array Using Given Indexes

```#include <bits/stdc++.h>
using namespace std;

//Function for reoreder elements based on index array
void Reorder(int array[], int index[], int N)
{
int temp[N];//auxilary array
//array[i] should present at (index[i]) index
for (int i=0; i<N; i++)
{
temp[index[i]] = array[i];
}
for (int i=0; i<N; i++)
{
array[i] = temp[i];
index[i] = i;
}
}
//function to print the given array
int PrintArray(int array[],int N)
{
for (int i=0; i<N; i++)
{
cout << array[i] << " ";
}
}
//Main function
int main()
{
int array[] = {50, 40, 70, 60, 90};
int index[] = {3,  0,  4,  1,  2};
int N = sizeof(array)/sizeof(array[0]);
cout << "Input array: \n";
PrintArray(array,N);
cout << "\nInput index array: \n";
PrintArray(index,N);
//Reordering by using function
Reorder(array,index,N);

cout << "\nOutput array: \n";
PrintArray(array,N);
cout << "\nOutput index array: \n";
PrintArray(index,N);
return 0;
}```
```Input array:
50 40 70 60 90
Input index array:
3 0 4 1 2
Output array:
40 60 90 50 70
Output index array:
0 1 2 3 4```

#### Java Program for Reorder Array Using Given Indexes

```import static java.lang.Math.pow;
import java.util.Arrays;
import java.util.Scanner;
class sum
{
//Function for reoreder elements based on index array
public static void Reorder(int array[], int index[], int N)
{
int temp[] = new int [N];//auxilary array
//array[i] should present at (index[i]) index
for (int i=0; i<N; i++)
{
temp[index[i]] = array[i];
}
for (int i=0; i<N; i++)
{
array[i] = temp[i];
index[i] = i;
}
}
//function to print the given array
public static void PrintArray(int array[],int N)
{
for (int i=0; i<N; i++)
{
System.out.print(array[i]+" ");
}
}
public static void main(String[] args)
{
Scanner sr = new Scanner(System.in);
int n = sr.nextInt();
int a[] = new int[n];
for(int i=0;i<n;i++)
{
a[i] = sr.nextInt();
}
int index[] = new int[n];
for(int i=0;i<n;i++)
{
index[i] = sr.nextInt();
}
System.out.println("Input array:");
PrintArray(a,n);
System.out.println("\nInput index array: ");
PrintArray(index,n);
//Reordering by using function
Reorder(a,index,n);
System.out.println("\nOutput array: ");
PrintArray(a,n);
System.out.println("\nOutput index array: ");
PrintArray(index,n);
}
}```
```5
9 3 5 1 7
0 4 2 3 1
```
```Input array:
9 3 5 1 7
Input index array:
0 4 2 3 1
Output array:
9 7 5 1 3
Output index array:
0 1 2 3 4```

### Complexity Analysis

#### Time complexity

O(n) where n is the size of the array. Here we traverse the array and put the element in the right position in the auxiliary array.

#### Space Complexity

O(n) where we use an auxiliary array for storing the elements in the right position.

## Approach 2

### Algorithm

Step 1: Create a function that takes the given arrays and reorders based on the index array.

Step 2: If index[i] = i, we need not change the position so, for all elements in the input array.
a)    Store values at correct position array[i] should be placed in dummy variables.
b)    Place array[i] at its position and update index value. (array[index[i]] = array[i])
c)    Copy old values to current positions. array[i] = oldElementvalue and update index.

Step 3: call this function input arrays, to reorder them.

### Implementation

#### C++ Program for Reorder Array Using Given Indexes

```#include <bits/stdc++.h>
using namespace std;

//Function for reoreder elements based on index array
void Reorder(int array[], int index[], int N)
{
for(int i=0; i<N; i++)
{
while (index[i] != i)
{
//storing correct position values
int  oldIndexValue = index[index[i]];
char oldElementValue   = array[index[i]];
array[index[i]] = array[i];
index[index[i]] = index[i];
index[i] = oldIndexValue;
array[i]   = oldElementValue;
}
}
}
//function to print the given array
int PrintArray(int array[],int N)
{
for (int i=0; i<N; i++)
{
cout << array[i] << " ";
}
}
//Main Function
int main()
{
int array[] = {50, 40, 70, 60, 90};
int index[] = {3,  0,  4,  1,  2};
int N = sizeof(array)/sizeof(array[0]);
cout << "Input array: \n";
PrintArray(array,N);
cout << "\nInput index array: \n";
PrintArray(index,N);
//Reordering by using function
Reorder(array,index,N);

cout << "\nOutput array: \n";
PrintArray(array,N);
cout << "\nOutput index array: \n";
PrintArray(index,N);
return 0;
}```
```Input array:
50 40 70 60 90
Input index array:
3 0 4 1 2
Output array:
40 60 90 50 70
Output index array:
0 1 2 3 4```

#### Java Program for Reorder Array Using Given Indexes

```import java.util.Scanner;
class sum
{
//Function for reoreder elements based on index array
public static void Reorder(int array[], int index[], int N)
{
for(int i=0; i<N; i++)
{
while (index[i] != i)
{
//storing correct position values
int  oldIndexValue = index[index[i]];
int oldElementValue   = array[index[i]];
array[index[i]] = array[i];
index[index[i]] = index[i];
index[i] = oldIndexValue;
array[i]   = oldElementValue;
}
}
}
//function to print the given array
public static void PrintArray(int array[],int N)
{
for (int i=0; i<N; i++)
{
System.out.print(array[i]+" ");
}
}
public static void main(String[] args)
{
Scanner sr = new Scanner(System.in);
int n = sr.nextInt();
int a[] = new int[n];
for(int i=0;i<n;i++)
{
a[i] = sr.nextInt();
}
int index[] = new int[n];
for(int i=0;i<n;i++)
{
index[i] = sr.nextInt();
}
System.out.println("Input array:");
PrintArray(a,n);
System.out.println("\nInput index array: ");
PrintArray(index,n);
//Reordering by using function
Reorder(a,index,n);
System.out.println("\nOutput array: ");
PrintArray(a,n);
System.out.println("\nOutput index array: ");
PrintArray(index,n);
}
}```
```5
1 2 3 4 5
4 3 2 1 0
```
```Input array:
1 2 3 4 5
Input index array:
4 3 2 1 0
Output array:
5 4 3 2 1
Output index array:
0 1 2 3 4```

### Complexity Analysis

#### Time complexity

O(n) where n is the size of the array. Here also we traverse the array one time that why the time complexity is linear.

#### Space Complexity

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

References

Translate »