Open In App

Reorder an array according to given indexes

Last Updated : 04 May, 2025
Suggest changes
Share
Like Article
Like
Report

Given two integer arrays of the same length, arr[] and index[], the task is to reorder the elements in arr[] such that after reordering, each element from arr[i] moves to the position index[i]. The new arrangement reflects the values being placed at their target indices, as described by index[] array.

Example: 

Input: arr[] = [10, 11, 12], index[] = [1, 0, 2]
Output: 11 10 12
Explanation: 10 moves to position 1, 11 to 0, and 12 stays at 2.

Input: arr[] = [1, 2, 3, 4], index[] = [3, 2, 0, 1]
Output: 3 4 2 1
Explanation: 1 moves to 3, 2 to 2, 3 to 0, 4 to 1.

Input: arr[] = [50, 40, 70, 60, 90], index[] = [3,  0,  4,  1,  2]
Output: 40 60 90 50 70

Table of Content

[Naive Approach] Using Sorting - O(n*log(n)) Time and O(n) Space

The idea is to pair each element in arr[] with its target position from index[] as a 2D array. These pairs are then sorted by index, which arranges elements in the order they should appear in the final array. After sorting, we extract only the values (second part of each pair) to build the reordered array.

C++ 
// C++ program to reorder arr[] using index[] // using Naive approach #include <bits/stdc++.h> using namespace std; // Function to reorder arr based on index void reorderArray(vector<int> &arr,   vector<int> &index) {  // Pair each element with its target index  vector<vector<int>> paired;  for (int i = 0; i < arr.size(); i++) {  paired.push_back({index[i], arr[i]});  }  // Sort the pairs by index  sort(paired.begin(), paired.end());  // Rearrange arr based on sorted pairs  for (int i = 0; i < arr.size(); i++) {  arr[i] = paired[i][1];  } } // Driver code int main() {  vector<int> arr = {10, 11, 12};  vector<int> index = {1, 0, 2};  reorderArray(arr, index);    // Print the updated array  for (int i = 0; i < arr.size(); i++) {  cout << arr[i] << " ";  }  return 0; }
Java 
// Java program to reorder arr[] using index[] // using Naive approach import java.util.*; class GfG {  // Function to reorder arr based on index  static void reorderArray(int[] arr, int[] index) {  // Pair each element with its target index  List<int[]> paired = new ArrayList<>();  for (int i = 0; i < arr.length; i++) {  paired.add(new int[]{index[i], arr[i]});  }  // Sort the pairs by index  Collections.sort(paired, (a, b) -> Integer.compare(a[0], b[0]));  // Rearrange arr based on sorted pairs  for (int i = 0; i < arr.length; i++) {  arr[i] = paired.get(i)[1];  }  }  // Driver code  public static void main(String[] args) {  int[] arr = {10, 11, 12};  int[] index = {1, 0, 2};  reorderArray(arr, index);  // Print the updated array  for (int i = 0; i < arr.length; i++) {  System.out.print(arr[i] + " ");  }  } }
Python 
# Python program to reorder arr[] using index[] # using Naive approach def reorderArray(arr, index): # Pair each element with its target index paired = [] for i in range(len(arr)): paired.append([index[i], arr[i]]) # Sort the pairs by index paired.sort() # Rearrange arr based on sorted pairs for i in range(len(arr)): arr[i] = paired[i][1] # Driver code if __name__ == "__main__": arr = [10, 11, 12] index = [1, 0, 2] reorderArray(arr, index) # Print the updated array print(" ".join(map(str, arr)))
C# 
// C# program to reorder arr[] using index[] // using Naive approach using System; using System.Collections.Generic; class GfG {  // Function to reorder arr based on index  static void reorderArray(int[] arr, int[] index) {  // Pair each element with its target index  List<int[]> paired = new List<int[]>();  for (int i = 0; i < arr.Length; i++) {  paired.Add(new int[] { index[i], arr[i] });  }  // Sort the pairs by index  paired.Sort((a, b) => a[0].CompareTo(b[0]));  // Rearrange arr based on sorted pairs  for (int i = 0; i < arr.Length; i++) {  arr[i] = paired[i][1];  }  }  // Driver code  public static void Main() {  int[] arr = {10, 11, 12};  int[] index = {1, 0, 2};  reorderArray(arr, index);  // Print the updated array  for (int i = 0; i < arr.Length; i++) {  Console.Write(arr[i] + " ");  }  } }
JavaScript 
// JavaScript program to reorder arr[] using index[] // using Naive approach function reorderArray(arr, index) {  // Pair each element with its target index  let paired = [];  for (let i = 0; i < arr.length; i++) {  paired.push([index[i], arr[i]]);  }  // Sort the pairs by index  paired.sort((a, b) => a[0] - b[0]);  // Rearrange arr based on sorted pairs  for (let i = 0; i < arr.length; i++) {  arr[i] = paired[i][1];  } } // Driver code let arr = [10, 11, 12]; let index = [1, 0, 2]; reorderArray(arr, index); // Print the updated array console.log(arr.join(" "));

Output
11 10 12

[Better Approach] Using an Auxiliary Array - O(n) Time and O(n) Space

The idea is to reorder using an auxiliary array to temporarily hold the reordered elements by placing each element at the target index. Afterward, the reordered values are copied back into the original arr[].

C++ 
// C++ program to reorder arr[] using index[] // using Auxiliary Array approach #include <bits/stdc++.h> using namespace std; // Function to reorder arr based on index void reorderArray(vector<int> &arr,   vector<int> &index) {  // Create an auxiliary array to hold   // the reordered elements  vector<int> reordered(arr.size());  // Place each element from arr[] at   // the position specified in index[]  for (int i = 0; i < arr.size(); i++) {  reordered[index[i]] = arr[i];  }  // Copy the reordered array back to arr[]  for (int i = 0; i < arr.size(); i++) {  arr[i] = reordered[i];  } } // Driver code int main() {  vector<int> arr = {10, 11, 12};  vector<int> index = {1, 0, 2};  reorderArray(arr, index);  // Print the updated array  for (int i = 0; i < arr.size(); i++) {  cout << arr[i] << " ";  }  return 0; }
Java 
// Java program to reorder arr[] using index[] // using Auxiliary Array approach class GfG {  // Function to reorder arr based on index  static void reorderArray(int[] arr, int[] index) {  // Create an auxiliary array to hold   // the reordered elements  int[] reordered = new int[arr.length];  // Place each element from arr[] at   // the position specified in index[]  for (int i = 0; i < arr.length; i++) {  reordered[index[i]] = arr[i];  }  // Copy the reordered array back to arr[]  for (int i = 0; i < arr.length; i++) {  arr[i] = reordered[i];  }  }  // Driver code  public static void main(String[] args) {  int[] arr = {10, 11, 12};  int[] index = {1, 0, 2};  reorderArray(arr, index);  // Print the updated array  for (int i = 0; i < arr.length; i++) {  System.out.print(arr[i] + " ");  }  } }
Python 
# Python program to reorder arr[] using index[] # using Auxiliary Array approach # Function to reorder arr based on index def reorderArray(arr, index): # Create an auxiliary array to hold  # the reordered elements reordered = [0] * len(arr) # Place each element from arr[] at  # the position specified in index[] for i in range(len(arr)): reordered[index[i]] = arr[i] # Copy the reordered array back to arr[] for i in range(len(arr)): arr[i] = reordered[i] # Driver code if __name__ == "__main__": arr = [10, 11, 12] index = [1, 0, 2] reorderArray(arr, index) # Print the updated array for i in range(len(arr)): print(arr[i], end=' ')
C# 
// C# program to reorder arr[] using index[] // using Auxiliary Array approach using System; class GfG {  // Function to reorder arr based on index  static void reorderArray(int[] arr, int[] index) {  // Create an auxiliary array to hold   // the reordered elements  int[] reordered = new int[arr.Length];  // Place each element from arr[] at   // the position specified in index[]  for (int i = 0; i < arr.Length; i++) {  reordered[index[i]] = arr[i];  }  // Copy the reordered array back to arr[]  for (int i = 0; i < arr.Length; i++) {  arr[i] = reordered[i];  }  }  // Driver code  public static void Main() {  int[] arr = {10, 11, 12};  int[] index = {1, 0, 2};  reorderArray(arr, index);  // Print the updated array  for (int i = 0; i < arr.Length; i++) {  Console.Write(arr[i] + " ");  }  } }
JavaScript 
// JavaScript program to reorder arr[] using index[] // using Auxiliary Array approach // Function to reorder arr based on index function reorderArray(arr, index) {  // Create an auxiliary array to hold   // the reordered elements  let reordered = new Array(arr.length);  // Place each element from arr[] at   // the position specified in index[]  for (let i = 0; i < arr.length; i++) {  reordered[index[i]] = arr[i];  }  // Copy the reordered array back to arr[]  for (let i = 0; i < arr.length; i++) {  arr[i] = reordered[i];  } } // Driver code let arr = [10, 11, 12]; let index = [1, 0, 2]; reorderArray(arr, index); // Print the updated array for (let i = 0; i < arr.length; i++) {  process.stdout.write(arr[i] + " "); }

Output
11 10 12

[Expected Approach - 1] Using Cyclic Sort - O(n) Time and O(1) Space

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.

Steps to implement the above idea:

  • Start a while loop with variable i = 0 and continue until i < length(arr), to process every element.
  • For each element, check if it's already in the correct position using index[i] == i to avoid unnecessary swaps.
  • If it is, just increment i to proceed to the next position, as the current one is already placed correctly.
  • If not, perform a manual swap of arr[i] and arr[index[i]] using a temporary variable to avoid data loss.
  • Alongside, manually swap index[i] with index[index[i]] to maintain synchronization between the index and value arrays.
  • Repeat this process until all elements are at their correct index according to the index[] array, ensuring correctness.
  • Once the loop completes, print the final reordered arr[] which now matches the intended layout defined by index[].
C++ 
// C++ program to reorder arr[] using index[] // using Cyclic Sort approach  #include <bits/stdc++.h> using namespace std; // Function to reorder arr based on index void reorderArray(vector<int> &arr,   vector<int> &index) {  int i = 0;  // Perform cyclic swaps until all elements  // are placed at their correct index  while (i < arr.size()) {  // If current index is already   // correct, move on  if (index[i] == i) {  i++;  }  // Otherwise, swap arr[i] with arr[index[i]]  // and update index[i] accordingly  else {  swap(arr[i], arr[index[i]]);  swap(index[i], index[index[i]]);  }  } } // Driver code int main() {  vector<int> arr = {10, 11, 12};  vector<int> index = {1, 0, 2};  reorderArray(arr, index);  // Print the updated array  for (int i = 0; i < arr.size(); i++) {  cout << arr[i] << " ";  }  return 0; }
Java 
// Java program to reorder arr[] using index[] // using Cyclic Sort approach  class GfG {  // Function to reorder arr based on index  static void reorderArray(int[] arr, int[] index) {  int i = 0;  // Perform cyclic swaps until all elements  // are placed at their correct index  while (i < arr.length) {  // If current index is already   // correct, move on  if (index[i] == i) {  i++;  }  // Otherwise, swap arr[i] with arr[index[i]]  // and update index[i] accordingly  else {  int temp1 = arr[i];  arr[i] = arr[index[i]];  arr[index[i]] = temp1;  int temp2 = index[i];  index[i] = index[temp2];  index[temp2] = temp2;  }  }  }  // Driver code  public static void main(String[] args) {  int[] arr = {10, 11, 12};  int[] index = {1, 0, 2};  reorderArray(arr, index);  // Print the updated array  for (int i = 0; i < arr.length; i++) {  System.out.print(arr[i] + " ");  }  } }
Python 
# Python program to reorder arr[] using index[] # using Cyclic Sort approach  def reorderArray(arr, index): i = 0 # Perform cyclic swaps until all elements # are placed at their correct index while i < len(arr): # If current index is already  # correct, move on if index[i] == i: i += 1 # Otherwise, swap arr[i] with arr[index[i]] # and update index[i] accordingly else: temp1 = arr[i] arr[i] = arr[index[i]] arr[index[i]] = temp1 temp2 = index[i] index[i] = index[temp2] index[temp2] = temp2 # Driver code if __name__ == "__main__": arr = [10, 11, 12] index = [1, 0, 2] reorderArray(arr, index) # Print the updated array for i in range(len(arr)): print(arr[i], end=' ')
C# 
// C# program to reorder arr[] using index[] // using Cyclic Sort approach  using System; class GfG {  // Function to reorder arr based on index  public static void reorderArray(int[] arr, int[] index) {  int i = 0;  // Perform cyclic swaps until all elements  // are placed at their correct index  while (i < arr.Length) {  // If current index is already   // correct, move on  if (index[i] == i) {  i++;  }  // Otherwise, swap arr[i] with arr[index[i]]  // and update index[i] accordingly  else {  int temp1 = arr[i];  arr[i] = arr[index[i]];  arr[index[i]] = temp1;  int temp2 = index[i];  index[i] = index[temp2];  index[temp2] = temp2;  }  }  }  // Driver code  public static void Main() {  int[] arr = {10, 11, 12};  int[] index = {1, 0, 2};  reorderArray(arr, index);  // Print the updated array  for (int i = 0; i < arr.Length; i++) {  Console.Write(arr[i] + " ");  }  } }
JavaScript 
// JavaScript program to reorder arr[] using index[] // using Cyclic Sort approach  function reorderArray(arr, index) {  let i = 0;  // Perform cyclic swaps until all elements  // are placed at their correct index  while (i < arr.length) {  // If current index is already   // correct, move on  if (index[i] === i) {  i++;  }  // Otherwise, swap arr[i] with arr[index[i]]  // and update index[i] accordingly  else {  let temp1 = arr[i];  arr[i] = arr[index[i]];  arr[index[i]] = temp1;  let temp2 = index[i];  index[i] = index[temp2];  index[temp2] = temp2;  }  } } // Driver code let arr = [10, 11, 12]; let index = [1, 0, 2]; reorderArray(arr, index); // Print the updated array for (let i = 0; i < arr.length; i++) {  process.stdout.write(arr[i] + " "); }

Output
11 10 12

[Expected Approach - 2] Using Mathematics - O(n) Time and O(1) Space

The idea is to reorder elements in-place without using extra space by encoding two numbers (original and new) into a single number. Since each element in arr[] is less than or equal to the maximum value, we pick value = max + 1 to ensure uniqueness when combining.

We update arr[index[i]] using -> arr[index[i]] += (arr[i] % value) * value, which embeds both current and new values in the same cell.

  • The % value ensures we use the original value even after updates.
  • The * value shifts the new value to a higher place (like storing digits).

In the final step, dividing every element by value removes the original part and leaves only the reordered value

C++ 
// C++ program to reorder arr[] using index[] // using Mathematical Encoding  #include <bits/stdc++.h> using namespace std; // Function to reorder arr based on index void reorderArray(vector<int> &arr,   vector<int> &index) {  int n = arr.size();  // Find the maximum value  int maxVal = arr[0];  for (int i = 1; i < n; i++) {  if (arr[i] > maxVal) {  maxVal = arr[i];  }  }  // Set value as max + 1  int value = maxVal + 1;  // Encode both old and new   // values at index[i]  for (int i = 0; i < n; i++) {  arr[index[i]] += (arr[i] % value) * value;  }  // Decode to get the reordered values  for (int i = 0; i < n; i++) {  arr[i] = arr[i] / value;  } } // Driver code int main() {  vector<int> arr = {10, 11, 12};  vector<int> index = {1, 0, 2};  reorderArray(arr, index);  // Print the updated array  for (int i = 0; i < arr.size(); i++) {  cout << arr[i] << " ";  }  return 0; }
Java 
// Java program to reorder arr[] using index[] // using Mathematical Encoding  class GfG {  // Function to reorder arr based on index  static void reorderArray(int[] arr, int[] index) {  int n = arr.length;  // Find the maximum value  int maxVal = arr[0];  for (int i = 1; i < n; i++) {  if (arr[i] > maxVal) {  maxVal = arr[i];  }  }  // Set value as max + 1  int value = maxVal + 1;  // Encode both old and new   // values at index[i]  for (int i = 0; i < n; i++) {  arr[index[i]] += (arr[i] % value) * value;  }  // Decode to get the reordered values  for (int i = 0; i < n; i++) {  arr[i] = arr[i] / value;  }  }  // Driver code  public static void main(String[] args) {  int[] arr = {10, 11, 12};  int[] index = {1, 0, 2};  reorderArray(arr, index);  // Print the updated array  for (int i = 0; i < arr.length; i++) {  System.out.print(arr[i] + " ");  }  } }
Python 
# Python program to reorder arr[] using index[] # using Mathematical Encoding  def reorderArray(arr, index): n = len(arr) # Find the maximum value maxVal = arr[0] for i in range(1, n): if arr[i] > maxVal: maxVal = arr[i] # Set value as max + 1 value = maxVal + 1 # Encode both old and new  # values at index[i] for i in range(n): arr[index[i]] += (arr[i] % value) * value # Decode to get the reordered values for i in range(n): arr[i] = arr[i] // value # Driver code if __name__ == "__main__": arr = [10, 11, 12] index = [1, 0, 2] reorderArray(arr, index) # Print the updated array for i in range(len(arr)): print(arr[i], end=' ')
C# 
// C# program to reorder arr[] using index[] // using Mathematical Encoding  using System; class GfG {  // Function to reorder arr based on index  public static void reorderArray(int[] arr,   int[] index) {  int n = arr.Length;  // Find the maximum value  int maxVal = arr[0];  for (int i = 1; i < n; i++) {  if (arr[i] > maxVal) {  maxVal = arr[i];  }  }  // Set value as max + 1  int value = maxVal + 1;  // Encode both old and new   // values at index[i]  for (int i = 0; i < n; i++) {  arr[index[i]] += (arr[i] % value) * value;  }  // Decode to get the reordered values  for (int i = 0; i < n; i++) {  arr[i] = arr[i] / value;  }  }  // Driver code  public static void Main() {  int[] arr = {10, 11, 12};  int[] index = {1, 0, 2};  reorderArray(arr, index);  // Print the updated array  for (int i = 0; i < arr.Length; i++) {  Console.Write(arr[i] + " ");  }  } }
JavaScript 
// JavaScript program to reorder arr[] using index[] // using Mathematical Encoding  function reorderArray(arr, index) {  let n = arr.length;  // Find the maximum value  let maxVal = arr[0];  for (let i = 1; i < n; i++) {  if (arr[i] > maxVal) {  maxVal = arr[i];  }  }  // Set value as max + 1  let value = maxVal + 1;  // Encode both old and new   // values at index[i]  for (let i = 0; i < n; i++) {  arr[index[i]] += (arr[i] % value) * value;  }  // Decode to get the reordered values  for (let i = 0; i < n; i++) {  arr[i] = Math.floor(arr[i] / value);  } } // Driver code let arr = [10, 11, 12]; let index = [1, 0, 2]; reorderArray(arr, index); // Print the updated array for (let i = 0; i < arr.length; i++) {  process.stdout.write(arr[i] + " "); }

Output
11 10 12

Next Article
Find the smallest missing number

K

kartik

Similar Reads

Article Tags :
Practice Tags :
We use cookies to ensure you have the best browsing experience on our website. By using our site, you acknowledge that you have read and understood our Cookie Policy & Privacy Policy  Cookies are not collected in the GeeksforGeeks mobile applications.
Lightbox