Reorder array using given indexes in C++
Reorder array using given indexes in C++
In C++ programming, there are many real-life problems where we need to rearrange or reorder an array based on a different pattern. One such problem is to reorder an array using given indexes.
Imagine you are shuffling cards or seating people according to a new order – this is what this problem is about.
Let’s understand how to do it efficiently using multiple approaches.
Problem Definition - Reorder array using given indexes
We are given two arrays:
- arr[] → an array that we want to reorder.
- index[] → tells us the new positions of the elements from arr[].
Your task is to reorder the arr[] according to the index[] so that each element of arr[] moves to the position given in index[].
Example:
- arr[] = {50, 40, 70, 60, 90}
- index[] = {3, 0, 4, 1, 2}
Output:
arr[] = {40, 60, 90, 50, 70}
Explanation:
- 50 moves to index 3 → arr[3] = 50
- 40 moves to index 0 → arr[0] = 40
- 70 moves to index 4 → arr[4] = 70
- 60 moves to index 1 → arr[1] = 60
- 90 moves to index 2 → arr[2] = 90
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Method for Solving Reorder array using given indexes in C++
List of Methods to solve Reorder array using given indexes:
- Method 1: Naive Approach using Sorting
- Method 2: Using an Auxiliary Array
- Method 3: Cyclic Sort (In-place)
- Method 4: Using Mathematics (Index Encoding)
Method 1: Naive Approach using Sorting
Algorithm:
Create a pair of elements and their indexes.
Sort based on the index.
Extract the values from sorted pairs.
Time Complexity: O(n logn)
Space Complexity: O(n)
Code:
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
void reorder(vector& arr, vector& index) {
int n = arr.size();
vector<pair<int, int>> paired;
for (int i = 0; i < n; i++) {
paired.push_back({index[i], arr[i]});
}
sort(paired.begin(), paired.end());
for (int i = 0; i < n; i++) {
arr[i] = paired[i].second;
}
}
int main() {
vector arr = {50, 40, 70, 60, 90};
vector index = {3, 0, 4, 1, 2};
reorder(arr, index);
for (int val : arr)
cout << val << " ";
return 0;
}
40 60 90 50 70
More Methods for Reorder array using given indexes in C++
Method 2: Using an Auxiliary Array
Algorithm:
Create a temporary array.
Place each element of arr[] at the correct index using index[].
Copy temp back to arr.
Time Complexity: O(n)
Space Complexity: O(n)
Code:
#include<iostream>
#include<vector>
using namespace std;
void reorder(vector& arr, vector& index) {
int n = arr.size();
vector temp(n);
for (int i = 0; i < n; i++) {
temp[index[i]] = arr[i];
}
arr = temp;
}
int main() {
vector arr = {50, 40, 70, 60, 90};
vector index = {3, 0, 4, 1, 2};
reorder(arr, index);
for (int val : arr)
cout << val << " ";
return 0;
}40 60 90 50 70
Method 3: Cyclic Sort (In-place)
Algorithm:
Use cyclic swapping.
While index[i] ≠ i:
Swap elements in arr and index until they match.
Time Complexity: O(n)
Space Complexity: O(1)
Code:
#include<iostream>
#include<vector>
using namespace std;
void reorder(vector& arr, vector& index) {
int n = arr.size();
for (int i = 0; i < n; i++) {
while (index[i] != i) {
swap(arr[i], arr[index[i]]);
swap(index[i], index[index[i]]);
}
}
}
int main() {
vector arr = {50, 40, 70, 60, 90};
vector index = {3, 0, 4, 1, 2};
reorder(arr, index);
for (int val : arr)
cout << val << " ";
return 0;
}
40 60 90 50 70
Method 4: Using Mathematics (Index Encoding)
Algorithm:
Add (arr[index[i]] % n) * n to each element.
Divide each element by n at the end to get the final result.
This method requires index values to be unique and within 0 to n-1.
Time Complexity: O(n)
Space Complexity: O(1)
Code:
#include<iostream>
#include<vector>
using namespace std;
void reorder(vector& arr, vector& index) {
int n = arr.size();
for (int i = 0; i < n; i++) {
arr[i] = arr[i] + (arr[index[i]] % 10000) * 10000;
}
for (int i = 0; i < n; i++) {
arr[i] = arr[i] / 10000;
}
}
int main() {
vector arr = {50, 40, 70, 60, 90};
vector index = {3, 0, 4, 1, 2};
reorder(arr, index);
for (int val : arr)
cout << val << " ";
return 0;
}
Output:
40 60 90 50 70
Fact about – Reordering array using index
Final Thoughts:
Reordering an array using given indexes is an important technique in C++ that helps us rearrange the elements of an array exactly how we want. Instead of moving elements randomly, the index array tells us the new position for each element. This makes the process clear and organized.
Whether you create a new array or reorder the original one, this method is efficient and easy to understand. Learning this concept not only improves your skills with arrays but also prepares you for coding challenges and interviews where such problems are common.
FAQs
Reordering an array using given indexes helps rearrange elements to a new order based on a separate index array, allowing flexible and controlled repositioning of elements without losing data.
Yes, it is possible to reorder the array in-place, but it requires careful handling to avoid overwriting elements before they are moved. Otherwise, using extra space like a temporary array is simpler and safer.
The index array provides the new position for each element in the original array, guiding where each element should be placed in the reordered array.
This technique is useful in sorting algorithms, data rearrangement tasks, memory management, and solving coding interview problems where elements must be rearranged based on specific rules.
Yes, this method is efficient since it directly moves elements based on their target positions. Using a temporary array, the time complexity is generally O(n), which is suitable even for large datasets.
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
