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;// Comparator function to sort pairs based on the second// elementbool comp(const pair<int, int>& v1, const pair<int, int>& v2){ // Sort in ascending order of index values return v1.second < v2.second;}// Function to reorder elements of arr[] according to// index[]void reorder(int arr[], int index[], int n){ // Create a vector of pairs, where each pair stores the // original element (arr[i]) and its corresponding index // (index[i]) vector<pair<int, int> > a(n); for (int i = 0; i < n; i++) { a[i].first = arr[i]; a[i].second = index[i]; } // Sort the vector of pairs based on the second element // (index) using the comp() comparator function sort(a.begin(), a.end(), comp); // Copy the sorted elements back to the original arr[] for (int i = 0; i < n; i++) { arr[i] = a[i].first; }}// Driver programint main(){ int arr[] = { 50, 40, 70, 60, 90 }; int index[] = { 3, 0, 4, 1, 2 }; int n = sizeof(arr) / sizeof(arr[0]); // Call the reorder function to rearrange elements in // arr[] based on index[] 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 { // Function to reorder elements of arr[] according to // index[] 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]; } // Copy the reordered elements back to the original // arr[] 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; // Call the Reorder function to rearrange elements // in arr[] based on index[] 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++
// C++ program to sort an array according to given// indexes#include<iostream>using namespace std;// Function to reorder elements of arr[] according// to index[]void reorder(int arr[], int index[], int n){ int temp[n]; // arr[i] should be present at index[i] index for (int i=0; i<n; i++) temp[index[i]] = arr[i]; // Copy temp[] to arr[] for (int i=0; i<n; i++) { arr[i] = temp[i]; index[i] = i; }}// Driver programint 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
//Java to find positions of zeroes flipping which// produces maximum number of consecutive 1'simport 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}; // Method to reorder elements of arr[] according // to index[] static void reorder() { int temp[] = new int[arr.length]; // arr[i] should be present at index[i] index for (int i=0; i<arr.length; i++) temp[index[i]] = arr[i]; // Copy temp[] to arr[] for (int i=0; i<arr.length; i++) { arr[i] = temp[i]; index[i] = i; } } // Driver method to test the above function 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
# Python3 program to sort# an array according to given# indexes# Function to reorder# elements of arr[] according# to index[]def reorder(arr,index, n): temp = [0] * n; # arr[i] should be # present at index[i] index for i in range(0,n): temp[index[i]] = arr[i] # Copy temp[] to arr[] for i in range(0,n): arr[i] = temp[i] index[i] = i # Driver programarr = [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 = " ")# This code is contributed by# Smitha Dinesh Semwal |
C#
// C# to find positions of zeroes flipping which// produces maximum number of consecutive 1'susing System; public class Test{ static int []arr = new int[]{50, 40, 70, 60, 90}; static int []index = new int[]{3, 0, 4, 1, 2}; // Method to reorder elements of arr[] according // to index[] static void reorder() { int []temp = new int[arr.Length]; // arr[i] should be present at index[i] index for (int i=0; i<arr.Length; i++) temp[index[i]] = arr[i]; // Copy temp[] to arr[] for (int i=0; i<arr.Length; i++) { arr[i] = temp[i]; index[i] = i; } } // Driver method to test the above function 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)); }}/*This code is contributed by 29AjayKumar*/ |
Javascript
<script> // JavaScript program to sort an array according to given // indexes // Function to reorder elements of arr[] according // to index[] function reorder(arr, index, n) { var temp = [...Array(n)]; // arr[i] should be present at index[i] index for (var i = 0; i < n; i++) temp[index[i]] = arr[i]; // Copy temp[] to arr[] for (var i = 0; i < n; i++) { arr[i] = temp[i]; index[i] = i; } } // Driver program 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] + " "); // This code is contributed by rdtank. </script> |
PHP
<?php// PHP program to sort an array // according to given indexes// Function to reorder elements // of arr[] according to index[]function reorder($arr, $index, $n){ // $temp[$n]; // arr[i] should be present // at index[i] index for ($i = 0; $i < $n; $i++) { $temp[$index[$i]] = $arr[$i]; } // Copy temp[] to arr[] 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] . " ";}}// Driver Code$arr = array(50, 40, 70, 60, 90);$index = array(3, 0, 4, 1, 2);$n = sizeof($arr);reorder($arr, $index, $n);// This code is contributed// by Abby_akku?> |
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.
- While the current element’s index is not equal to its position (i.e., index[i] != i), perform the following steps:
- 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++
// sort an array according to given indexes#include<iostream>using namespace std;// Function to reorder elements of arr[] according// to index[]void reorder(int arr[], int index[], int n){ // Fix all elements one by one for (int i=0; i<n; i++) { // While index[i] and arr[i] are not fixed while (index[i] != i) { // Store values of the target (or correct) // position before placing arr[i] there int oldTargetI = index[index[i]]; char oldTargetE = arr[index[i]]; // Place arr[i] at its target (or correct) // position. Also copy corrected index for // new position arr[index[i]] = arr[i]; index[index[i]] = index[i]; // Copy old target values to arr[i] and // index[i] index[i] = oldTargetI; arr[i] = oldTargetE; } }}// Driver programint 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
//A O(n) time and O(1) extra space Java program to//sort an array according to given indexesimport 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}; // Method to reorder elements of arr[] according // to index[] static void reorder() { // Fix all elements one by one for (int i=0; i<arr.length; i++) { // While index[i] and arr[i] are not fixed while (index[i] != i) { // Store values of the target (or correct) // position before placing arr[i] there int oldTargetI = index[index[i]]; char oldTargetE = (char)arr[index[i]]; // Place arr[i] at its target (or correct) // position. Also copy corrected index for // new position arr[index[i]] = arr[i]; index[index[i]] = index[i]; // Copy old target values to arr[i] and // index[i] index[i] = oldTargetI; arr[i] = oldTargetE; } } } // Driver method to test the above function 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
# A O(n) time and O(1) extra space Python3 program to# sort an array according to given indexes# Function to reorder elements of arr[] according# to index[]def reorder(arr, index, n): # Fix all elements one by one for i in range(0,n): # While index[i] and arr[i] are not fixed while (index[i] != i): # Store values of the target (or correct) # position before placing arr[i] there oldTargetI = index[index[i]] oldTargetE = arr[index[i]] # Place arr[i] at its target (or correct) # position. Also copy corrected index for # new position arr[index[i]] = arr[i] index[index[i]] = index[i] # Copy old target values to arr[i] and # index[i] index[i] = oldTargetI arr[i] = oldTargetE# Driver programarr = [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=" ")# This code is contributed by# Smitha Dinesh Semwal |
C#
//A O(n) time and O(1) extra space C# program to//sort an array according to given indexesusing System; public class Test{ static int []arr = new int[]{50, 40, 70, 60, 90}; static int []index = new int[]{3, 0, 4, 1, 2}; // Method to reorder elements of arr[] according // to index[] static void reorder() { // Fix all elements one by one for (int i=0; i<arr.Length; i++) { // While index[i] and arr[i] are not fixed while (index[i] != i) { // Store values of the target (or correct) // position before placing arr[i] there int oldTargetI = index[index[i]]; char oldTargetE = (char)arr[index[i]]; // Place arr[i] at its target (or correct) // position. Also copy corrected index for // new position arr[index[i]] = arr[i]; index[index[i]] = index[i]; // Copy old target values to arr[i] and // index[i] index[i] = oldTargetI; arr[i] = oldTargetE; } } } // Driver method to test the above function 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)); }}// This code is contributed by PrinciRaj1992 |
Javascript
<script>// A O(n) time and O(1) extra space JavaScript program to// sort an array according to given indexes// Function to reorder elements of arr[] according// to index[]function reorder(arr, index, n){ // Fix all elements one by one for (let i=0; i<n; i++) { // While index[i] and arr[i] are not fixed while (index[i] != i) { // Store values of the target (or correct) // position before placing arr[i] there let oldTargetI = index[index[i]]; let oldTargetE = arr[index[i]]; // Place arr[i] at its target (or correct) // position. Also copy corrected index for // new position arr[index[i]] = arr[i]; index[index[i]] = index[i]; // Copy old target values to arr[i] and // index[i] index[i] = oldTargetI; arr[i] = oldTargetE; } }}// Driver program 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] + " ");// This code is contributed by Surbhi Tyagi.</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++
// C++ code for the above approach#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;}// result = (original + update%z*z) ..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;}// This code is contributed by lokesh |
Java
/*package whatever //do not write package name here */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] + " "); } // result = (original + update%z*z) .. 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
# Python implementation for the above approachdef printArray(arr): for i in range(len(arr)): print(arr[i], end=" ")# result = (original + update%z*z) ..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]//zdef findMax(arr): Max = float("-inf") for i in range(len(arr)): if(Max < arr[i]): Max = arr[i] return Maxarr = [23, 12, 20, 10, 23]index = [4, 0, 1, 2, 3]rearrange(arr, index)printArray(arr)# This code is contributed by lokesh |
C#
// C# implementation for the above approachusing System;public class GFG { static public void Main() { // Code 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] + " "); } // result = (original + update%z*z) .. 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; }}// This code is contributed by lokeshmvs21. |
Javascript
// JavaScript implementation for the above approachfunction printArray(){ for(let i = 0; i < arr.length; i++){ console.log(Math.trunc(arr[i]) + " "); }}// result = (original + update%z*z) ..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);// This code is contributed by lokeshmvs21. |
Output
12 20 10 23 23
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
