Given two integer arrays of the same size, “arr[]” and “index[]”, reorder elements in “arr[]” according to the given index array.
Example:
Input: arr[] = [10, 11, 12];
index[] = [1, 0, 2];
Output: arr[] = [11, 10, 12]
index[] = [0, 1, 2]
Input: arr[] = [50, 40, 70, 60, 90]
index[] = [3, 0, 4, 1, 2]
Output: arr[] = [40, 60, 90, 50, 70]
index[] = [0, 1, 2, 3, 4]
Reorder an array according to given indexes using Sorting:
The idea is to use an array of pairs to associate elements from the arr[] array with their respective indices from the index[] array and then sort these pairs based on the indices.
Follow the steps to solve the problem:
- Create an array of pairs to and associate elements from the arr[] array with their respective indices from the index[].
- Then sort the array of pair according based on indices using comparator.
- Copy the rearranged elements back into the arr[] array, effectively reordering the elements according to the specified indices.
Below is the implementation of above approach:
C++
#include <bits/stdc++.h>
using namespace std;
bool comp( const pair< int , int >& v1,
const pair< int , int >& v2)
{
return v1.second < v2.second;
}
void reorder( int arr[], int index[], int n)
{
vector<pair< int , int > > a(n);
for ( int i = 0; i < n; i++) {
a[i].first = arr[i];
a[i].second = index[i];
}
sort(a.begin(), a.end(), comp);
for ( int i = 0; i < n; i++) {
arr[i] = a[i].first;
}
}
int main()
{
int arr[] = { 50, 40, 70, 60, 90 };
int index[] = { 3, 0, 4, 1, 2 };
int n = sizeof (arr) / sizeof (arr[0]);
reorder(arr, index, n);
cout << "Reordered array is: \n" ;
for ( int i = 0; i < n; i++)
cout << arr[i] << " " ;
return 0;
}
|
C#
using System;
class Program {
static void Reorder( int [] arr, int [] index)
{
int n = arr.Length;
int [] result = new int [n];
for ( int i = 0; i < n; i++) {
result[index[i]] = arr[i];
}
Array.Copy(result, arr, n);
}
static void Main()
{
int [] arr = { 50, 40, 70, 60, 90 };
int [] index = { 3, 0, 4, 1, 2 };
int n = arr.Length;
Reorder(arr, index);
Console.WriteLine( "Reordered array is:" );
Console.WriteLine( string .Join( " " , arr));
}
}
|
Output
Reordered array is:
40 60 90 50 70
Time Complexity: O(n log n)
Auxiliary Space: O(n)
Reorder an array according to given indexes using Auxiliary Array:
The idea is to use an auxiliary array temp[] of same size as given arrays. Traverse the given array and put all elements at their correct place in temp[] using index[].
Follow the steps to solve the problem:
- Create an auxiliary array temp[] to store the recorded array.
- Iterate through the given array arr[] and put all elements at their correct position in temp[] array using the index array.
- Copy the temp[] array to arr[] array.
Below is the implementation of above approach:
C++
#include<iostream>
using namespace std;
void reorder( int arr[], int index[], int n)
{
int temp[n];
for ( int i=0; i<n; i++)
temp[index[i]] = arr[i];
for ( int i=0; i<n; i++)
{
arr[i] = temp[i];
index[i] = i;
}
}
int main()
{
int arr[] = {50, 40, 70, 60, 90};
int index[] = {3, 0, 4, 1, 2};
int n = sizeof (arr)/ sizeof (arr[0]);
reorder(arr, index, n);
cout << "Reordered array is: \n" ;
for ( int i=0; i<n; i++)
cout << arr[i] << " " ;
}
|
Java
import java.util.Arrays;
class Test
{
static int arr[] = new int []{ 50 , 40 , 70 , 60 , 90 };
static int index[] = new int []{ 3 , 0 , 4 , 1 , 2 };
static void reorder()
{
int temp[] = new int [arr.length];
for ( int i= 0 ; i<arr.length; i++)
temp[index[i]] = arr[i];
for ( int i= 0 ; i<arr.length; i++)
{
arr[i] = temp[i];
index[i] = i;
}
}
public static void main(String[] args)
{
reorder();
System.out.println( "Reordered array is: " );
System.out.println(Arrays.toString(arr));
System.out.println( "Modified Index array is:" );
System.out.println(Arrays.toString(index));
}
}
|
Python3
def reorder(arr,index, n):
temp = [ 0 ] * n;
for i in range ( 0 ,n):
temp[index[i]] = arr[i]
for i in range ( 0 ,n):
arr[i] = temp[i]
index[i] = i
arr = [ 50 , 40 , 70 , 60 , 90 ]
index = [ 3 , 0 , 4 , 1 , 2 ]
n = len (arr)
reorder(arr, index, n)
print ( "Reordered array is:" )
for i in range ( 0 ,n):
print (arr[i],end = " " )
print ( "\nModified Index array is:" )
for i in range ( 0 ,n):
print (index[i],end = " " )
|
C#
using System;
public class Test{
static int []arr = new int []{50, 40, 70, 60, 90};
static int []index = new int []{3, 0, 4, 1, 2};
static void reorder()
{
int []temp = new int [arr.Length];
for ( int i=0; i<arr.Length; i++)
temp[index[i]] = arr[i];
for ( int i=0; i<arr.Length; i++)
{
arr[i] = temp[i];
index[i] = i;
}
}
public static void Main()
{
reorder();
Console.WriteLine( "Reordered array is: " );
Console.WriteLine( string .Join( "," , arr));
Console.WriteLine( "Modified Index array is:" );
Console.WriteLine( string .Join( "," , index));
}
}
|
Javascript
<script>
function reorder(arr, index, n) {
var temp = [...Array(n)];
for ( var i = 0; i < n; i++) temp[index[i]] = arr[i];
for ( var i = 0; i < n; i++) {
arr[i] = temp[i];
index[i] = i;
}
}
var arr = [50, 40, 70, 60, 90];
var index = [3, 0, 4, 1, 2];
var n = arr.length;
reorder(arr, index, n);
document.write( "Reordered array is: " );
document.write( "<br>" );
for ( var i = 0; i < n; i++) document.write(arr[i] + " " );
document.write( "<br>" );
document.write( "Modified Index array is: " );
document.write( "<br>" );
for ( var i = 0; i < n; i++) document.write(index[i] + " " );
</script>
|
PHP
<?php
function reorder( $arr , $index , $n )
{
for ( $i = 0; $i < $n ; $i ++)
{
$temp [ $index [ $i ]] = $arr [ $i ];
}
for ( $i = 0; $i < $n ; $i ++)
{
$arr [ $i ] = $temp [ $i ];
$index [ $i ] = $i ;
}
echo "Reordered array is: \n" ;
for ( $i = 0; $i < $n ; $i ++)
{
echo $arr [ $i ] . " " ;
}
echo "\nModified Index array is: \n" ;
for ( $i = 0; $i < $n ; $i ++)
{
echo $index [ $i ] . " " ;
}
}
$arr = array (50, 40, 70, 60, 90);
$index = array (3, 0, 4, 1, 2);
$n = sizeof( $arr );
reorder( $arr , $index , $n );
?>
|
Output
Reordered array is:
40 60 90 50 70
Time Complexity: O(n)
Auxiliary Space: O(n)
Reorder an array according to given indexes using Cyclic Sort:
The idea is use cyclic sort technique to reorder elements in the arr[] array based on the specified index[]. It iterates through the elements of arr[] and, for each element, continuously swaps it with the element at its correct position according to index[]. The process continues until each element is at its intended position, ensuring the desired order is achieved.
Follow the steps to solve the problem:
- Iterate through the array and do following for every element arr[i]:
- While the current element’s index is not equal to its position (i.e., index[i] != i), perform the following steps:
- Store the value and index of the target (correct) position before placing the current element there.
- Place the current element at its target position (arr[index[i]] and index[index[i]]), effectively swapping elements.
- Update the current element’s index and value with the stored target values.
- Continue this process for all elements in the array until each element is at its intended position according to the index[] array.
- The arr[] array will be reordered according to the specified indices in index[] after the cyclic sort is complete.
Below is the implementation of the above algorithm.
C++
#include<iostream>
using namespace std;
void reorder( int arr[], int index[], int n)
{
for ( int i=0; i<n; i++)
{
while (index[i] != i)
{
int oldTargetI = index[index[i]];
char oldTargetE = arr[index[i]];
arr[index[i]] = arr[i];
index[index[i]] = index[i];
index[i] = oldTargetI;
arr[i] = oldTargetE;
}
}
}
int main()
{
int arr[] = {50, 40, 70, 60, 90};
int index[] = {3, 0, 4, 1, 2};
int n = sizeof (arr)/ sizeof (arr[0]);
reorder(arr, index, n);
cout << "Reordered array is: \n" ;
for ( int i=0; i<n; i++)
cout << arr[i] << " " ;
return 0;
}
|
Java
import java.util.Arrays;
class Test
{
static int arr[] = new int []{ 50 , 40 , 70 , 60 , 90 };
static int index[] = new int []{ 3 , 0 , 4 , 1 , 2 };
static void reorder()
{
for ( int i= 0 ; i<arr.length; i++)
{
while (index[i] != i)
{
int oldTargetI = index[index[i]];
char oldTargetE = ( char )arr[index[i]];
arr[index[i]] = arr[i];
index[index[i]] = index[i];
index[i] = oldTargetI;
arr[i] = oldTargetE;
}
}
}
public static void main(String[] args)
{
reorder();
System.out.println( "Reordered array is: " );
System.out.println(Arrays.toString(arr));
System.out.println( "Modified Index array is:" );
System.out.println(Arrays.toString(index));
}
}
|
Python3
def reorder(arr, index, n):
for i in range ( 0 ,n):
while (index[i] ! = i):
oldTargetI = index[index[i]]
oldTargetE = arr[index[i]]
arr[index[i]] = arr[i]
index[index[i]] = index[i]
index[i] = oldTargetI
arr[i] = oldTargetE
arr = [ 50 , 40 , 70 , 60 , 90 ]
index = [ 3 , 0 , 4 , 1 , 2 ]
n = len (arr)
reorder(arr, index, n)
print ( "Reordered array is:" )
for i in range ( 0 , n):
print (arr[i],end = " " )
print ( "\nModified Index array is:" )
for i in range ( 0 , n):
print (index[i] ,end = " " )
|
C#
using System;
public class Test
{
static int []arr = new int []{50, 40, 70, 60, 90};
static int []index = new int []{3, 0, 4, 1, 2};
static void reorder()
{
for ( int i=0; i<arr.Length; i++)
{
while (index[i] != i)
{
int oldTargetI = index[index[i]];
char oldTargetE = ( char )arr[index[i]];
arr[index[i]] = arr[i];
index[index[i]] = index[i];
index[i] = oldTargetI;
arr[i] = oldTargetE;
}
}
}
public static void Main()
{
reorder();
Console.WriteLine( "Reordered array is: " );
Console.WriteLine(String.Join( " " ,arr));
Console.WriteLine( "Modified Index array is:" );
Console.WriteLine(String.Join( " " ,index));
}
}
|
Javascript
<script>
function reorder(arr, index, n)
{
for (let i=0; i<n; i++)
{
while (index[i] != i)
{
let oldTargetI = index[index[i]];
let oldTargetE = arr[index[i]];
arr[index[i]] = arr[i];
index[index[i]] = index[i];
index[i] = oldTargetI;
arr[i] = oldTargetE;
}
}
}
let arr = [50, 40, 70, 60, 90];
let index = [3, 0, 4, 1, 2];
let n = arr.length;
reorder(arr, index, n);
document.write( "Reordered array is: <br>" );
for (let i=0; i<n; i++)
document.write(arr[i] + " " );
document.write( "<br>Modified Index array is: <br>" );
for (let i=0; i<n; i++)
document.write(index[i] + " " );
</script>
|
Output
Reordered array is:
40 60 90 50 70
Time Complexity: O(n)
Auxiliary Space: O(1)
Reorder an array according to given indexes using Mathematics Approach:
Follow the steps to solve the problem by the above approach:
- Calculate the max(array, n) and value = max_value + 1; This is needed to identify the upper range of values present in the array as the modulus operation will always return a value from 0 to N-1 (used in next step for storing two elements together)
- For each element, place the element at index=i at it’s desired position at index=j such that it’s possible to retrieve both elements when needed. The following formula has been used to store the array[i] at array[j]
array[index[i]] = (array[index[i]] + array[i]%value*value)
- Once the elements are placed at each position, traverse the array once and update each element by element value.
Below is the implementation of the above algorithm.
C++
#include <climits>
#include <iostream>
using namespace std;
int findMax( int arr[], int n)
{
int Max = INT_MIN;
for ( int i = 0; i < n; i++) {
if (Max < arr[i])
Max = arr[i];
}
return Max;
}
void rearrange( int arr[], int index[], int n)
{
int z = findMax(arr, n) + 1;
for ( int i = 0; i < n; i++) {
arr[index[i]] = arr[index[i]] % z + arr[i] % z * z;
}
for ( int i = 0; i < n; i++) {
arr[i] = arr[i] / z;
}
}
int main()
{
int arr[] = { 23, 12, 20, 10, 23 };
int index[] = { 4, 0, 1, 2, 3 };
rearrange(arr, index, 5);
cout << "Reordered array is: \n" ;
for ( int i = 0; i < 5; i++)
cout << arr[i] << " " ;
return 0;
}
|
Java
import java.io.*;
class GFG {
public static void main(String[] args)
{
int arr[] = { 23 , 12 , 20 , 10 , 23 };
int index[] = { 4 , 0 , 1 , 2 , 3 };
rearrange(arr, index);
printArray(arr);
}
private static void printArray( int arr[])
{
for ( int i = 0 ; i < arr.length; i++)
System.out.print(arr[i] + " " );
}
private static void rearrange( int [] arr, int [] index)
{
int z = findMax(arr) + 1 ;
for ( int i = 0 ; i < arr.length; i++) {
arr[index[i]]
= arr[index[i]] % z + arr[i] % z * z;
}
for ( int i = 0 ; i < arr.length; i++) {
arr[i] = arr[i] / z;
}
}
private static int findMax( int [] arr)
{
int max = Integer.MIN_VALUE;
for ( int i = 0 ; i < arr.length; i++) {
if (max < arr[i])
max = arr[i];
}
return max;
}
}
|
Python3
def printArray(arr):
for i in range ( len (arr)):
print (arr[i], end = " " )
def rearrange(arr, index):
z = findMax(arr) + 1
for i in range ( len (arr)):
arr[index[i]] = arr[index[i]] % z + arr[i] % z * z
for i in range ( len (arr)):
arr[i] = arr[i] / / z
def findMax(arr):
Max = float ( "-inf" )
for i in range ( len (arr)):
if ( Max < arr[i]):
Max = arr[i]
return Max
arr = [ 23 , 12 , 20 , 10 , 23 ]
index = [ 4 , 0 , 1 , 2 , 3 ]
rearrange(arr, index)
printArray(arr)
|
C#
using System;
public class GFG {
static public void Main()
{
int [] arr = { 23, 12, 20, 10, 23 };
int [] index = { 4, 0, 1, 2, 3 };
rearrange(arr, index);
printArray(arr);
}
private static void printArray( int [] arr)
{
for ( int i = 0; i < arr.Length; i++)
Console.Write(arr[i] + " " );
}
private static void rearrange( int [] arr, int [] index)
{
int z = findMax(arr) + 1;
for ( int i = 0; i < arr.Length; i++) {
arr[index[i]]
= arr[index[i]] % z + arr[i] % z * z;
}
for ( int i = 0; i < arr.Length; i++) {
arr[i] = arr[i] / z;
}
}
private static int findMax( int [] arr)
{
int max = Int32.MinValue;
for ( int i = 0; i < arr.Length; i++) {
if (max < arr[i])
max = arr[i];
}
return max;
}
}
|
Javascript
function printArray(){
for (let i = 0; i < arr.length; i++){
console.log(Math.trunc(arr[i]) + " " );
}
}
function rearrange(arr, index){
var z = findMax(arr) + 1;
for (let i = 0; i < arr.length; i++){
arr[index[i]] = arr[index[i]] % z + arr[i] % z * z;
}
for (let i = 0; i < arr.length; i++){
arr[i] = arr[i]/z;
}
}
function findMax(arr){
let max = Number.MIN_VALUE;
for (let i = 0; i < arr.length; i++){
if (max < arr[i]){
max = arr[i];
}
}
return max;
}
let arr = [ 23, 12, 20, 10, 23 ];
let index = [ 4, 0, 1, 2, 3 ];
rearrange(arr, index);
printArray(arr);
|
Time Complexity: O(N)
Auxiliary Space: O(1)
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!