Reorder Array with Indices: Codes with Visualization
Sasank is a Technical Content Writer with a strong background in competitive programming. He has solved nearly 1500 problems on LeetCode and achieved top rankings in LeetCode Weekly Contests, including global ranks of 171, 196, 206, 308, 352, and more. His expertise in algorithms and problem-solving is also reflected in his active participation on platforms like Codeforces. Sasank enjoys sharing his technical knowledge and helping others learn by creating clear and accessible content.
Problem Statement
You are given two arrays: arr and indices. Both arrays have the same length. The indices array represents the new positions of the elements in arr. Your task is to reorder the elements in arr according to the positions specified in indices.
For example:
- If arr = [5, 3, 2, 1, 4] and indices = [4, 0, 1, 2, 3], then the reordered array should be [3, 2, 1, 4, 5].
- The element 5 (at index 0 in the original array) should go to index 4.
- The element 3 (at index 1 in the original array) should go to index 0, and so on.
Brute Force Approach
Explanation
The simplest way to tackle this problem is to create a new array of the same size as the original array. We then place each element of the original array at its designated position in the new array, as specified by the indices array.
The time complexity is O(n), where n is the length of the arrays, as we need to iterate through each element once. The space complexity is O(n) because we create an additional array to store the reordered elements.
We consider the test case arr = [5, 3, 2, 1, 4] and indices = [4, 0, 1, 2, 3]
i = 0 → indices[0] = 4 → result[4] = arr[0] = 5
→ result = [0, 0, 0, 0, 5]
i = 1 → indices[1] = 0 → result[0] = arr[1] = 3
→ result = [3, 0, 0, 0, 5]
i = 2 → indices[2] = 1 → result[1] = arr[2] = 2
→ result = [3, 2, 0, 0, 5]
i = 3 → indices[3] = 2 → result[2] = arr[3] = 1
→ result = [3, 2, 1, 0, 5]
i = 4 → indices[4] = 3 → result[3] = arr[4] = 4
→ result = [3, 2, 1, 4, 5]
Python Code
def reorder_array_brute_force(arr, indices):
# Create a new array of the same size
result = [0] * len(arr)
# Place each element at its new position
for i in range(len(arr)):
result[indices[i]] = arr[i]
# Copy the result back to the original array if needed
for i in range(len(arr)):
arr[i] = result[i]
return result
C++ Code
#include <vector>
std::vector<int> reorderArrayBruteForce(std::vector<int>& arr, std::vector<int>& indices) {
int n = arr.size();
// Create a new array of the same size
std::vector<int> result(n);
// Place each element at its new position
for (int i = 0; i < n; i++) {
result[indices[i]] = arr[i];
}
// Copy the result back to the original array if needed
for (int i = 0; i < n; i++) {
arr[i] = result[i];
}
return result;
}
Java Code
public static int[] reorderArrayBruteForce(int[] arr, int[] indices) {
int n = arr.length;
// Create a new array of the same size
int[] result = new int[n];
// Place each element at its new position
for (int i = 0; i < n; i++) {
result[indices[i]] = arr[i];
}
// Copy the result back to the original array if needed
for (int i = 0; i < n; i++) {
arr[i] = result[i];
}
return result;
}
Optimized Approach
Explanation
While our brute force approach is already O(n) time complexity, which is optimal for this problem, we can improve it by reordering the array in-place without using extra space.
The key insight is to use a cycle-following technique:
- Start with the first element and place it at its correct position.
- The element that was originally at that position gets displaced, so we place it at its correct position too.
- We continue this process, forming a cycle, until we return to the original position.
- We then move to the next unprocessed element and repeat.
However, this approach requires careful handling to avoid overwriting elements before they're processed. We'll use the array values themselves to track whether elements have been processed.
The time complexity remains O(n), but the space complexity improves to O(1) as we're making the changes in-place.
Consider the testcase arr = [5, 3, 2, 1, 4] and indices = [4, 0, 1, 2, 3]
If arr[i] should go to indices[i], we follow this trail like a linked cycle.
Once a cycle is done, mark elements as processed using negative encoding (-1 - value) so we don't visit again.
Loop 1: i = 0
- indices[0] = 4, not yet processed
- Start a cycle:
- current_val = arr[0] = 5
- current_idx = 0
Cycle 1:
- target_idx = indices[0] = 4
- next_val = arr[4] = 4
- Move 5 → arr[4] → arr = [5, 3, 2, 1, 5]
- Mark indices[0] = -1 - 4 = -5
- Update: current_val = 4, current_idx = 4
- target_idx = indices[4] = 3
- next_val = arr[3] = 1
- Move 4 → arr[3] → arr = [5, 3, 2, 4, 5]
- Mark indices[4] = -1 - 3 = -4
- Update: current_val = 1, current_idx = 3
- target_idx = indices[3] = 2
- next_val = arr[2] = 2
- Move 1 → arr[2] → arr = [5, 3, 1, 4, 5]
- Mark indices[3] = -1 - 2 = -3
- Update: current_val = 2, current_idx = 2
- target_idx = indices[2] = 1
- next_val = arr[1] = 3
- Move 2 → arr[1] → arr = [5, 2, 1, 4, 5]
- Mark indices[2] = -1 - 1 = -2
- Update: current_val = 3, current_idx = 1
- target_idx = indices[1] = 0
- next_val = arr[0] = 5
- Move 3 → arr[0] → arr = [3, 2, 1, 4, 5]
Mark indices[1] = -1 - 0 = -1
- Update: current_val = 5, current_idx = 0
→ Now indices[0] = -5 (already processed), cycle ends.
Final placement: arr[0] = 5
→ arr = [5, 2, 1, 4, 5] → but wait! This was already placed earlier. So we skip reassigning.
→ Also mark last index indices[0] = -5 (already done)
Loop 2 to 4:
- i = 1 to 4 → All indices[i] < 0 → skip, already processed
Restore indices
indices = [-5, -1, -2, -3, -4]
→ Convert back:
indices = [4, 0, 1, 2, 3]
arr = [3, 2, 1, 4, 5]
Same as brute force result ✅
But done in-place with no extra space (apart from a few variables).
<visualization-box>
Python Code
def reorder_array_optimized(arr, indices):
n = len(arr)
# For each position
for i in range(n):
# Skip if element is already at correct position or already processed
if indices[i] == i or indices[i] < 0:
continue
# Save the current element and its target position
current_val = arr[i]
current_idx = i
# Follow the cycle until we return to the original position
while indices[current_idx] != i:
# Find the target position for current element
target_idx = indices[current_idx]
# Store the element at the target position before overwriting
next_val = arr[target_idx]
# Move current element to its target position
arr[target_idx] = current_val
# Mark this index as processed by making it negative
indices[current_idx] = -1 - indices[current_idx]
# Move to the next element in the cycle
current_val = next_val
current_idx = target_idx
# Place the last element in the cycle
arr[i] = current_val
# Mark the last index as processed
indices[current_idx] = -1 - indices[current_idx]
# Restore the indices array (optional)
for i in range(n):
if indices[i] < 0:
indices[i] = -1 - indices[i]
return arr
C++ Code
#include <iostream>
#include <vector>
using namespace std;
vector<int> reorderArrayOptimized(vector<int>& arr, vector<int>& indices) {
int n = arr.size();
// For each position
for (int i = 0; i < n; i++) {
// Skip if element is already at correct position or already processed
if (indices[i] == i || indices[i] < 0) {
continue;
}
// Save the current element and its target position
int current_val = arr[i];
int current_idx = i;
// Follow the cycle until we return to the original position
while (indices[current_idx] != i) {
// Find the target position for current element
int target_idx = indices[current_idx];
// Store the element at the target position before overwriting
int next_val = arr[target_idx];
// Move current element to its target position
arr[target_idx] = current_val;
// Mark this index as processed by making it negative
indices[current_idx] = -1 - indices[current_idx];
// Move to the next element in the cycle
current_val = next_val;
current_idx = target_idx;
}
// Place the last element in the cycle
arr[i] = current_val;
// Mark the last index as processed
indices[current_idx] = -1 - indices[current_idx];
}
// Restore the indices array (optional)
for (int i = 0; i < n; i++) {
if (indices[i] < 0) {
indices[i] = -1 - indices[i];
}
}
return arr;
}
Java Code
public static int[] reorderArrayOptimized(int[] arr, int[] indices) {
int n = arr.length;
// For each position
for (int i = 0; i < n; i++) {
// Skip if element is already at correct position or already processed
if (indices[i] == i || indices[i] < 0) {
continue;
}
// Save the current element and its target position
int currentVal = arr[i];
int currentIdx = i;
// Follow the cycle until we return to the original position
while (indices[currentIdx] != i) {
// Find the target position for current element
int targetIdx = indices[currentIdx];
// Store the element at the target position before overwriting
int nextVal = arr[targetIdx];
// Move current element to its target position
arr[targetIdx] = currentVal;
// Mark this index as processed by making it negative
indices[currentIdx] = -1 - indices[currentIdx];
// Move to the next element in the cycle
currentVal = nextVal;
currentIdx = targetIdx;
}
// Place the last element in the cycle
arr[i] = currentVal;
// Mark the last index as processed
indices[currentIdx] = -1 - indices[currentIdx];
}
// Restore the indices array (optional)
for (int i = 0; i < n; i++) {
if (indices[i] < 0) {
indices[i] = -1 - indices[i];
}
}
return arr;
}
Conclusion
This problem teaches us about manipulating arrays and tracking element positions. While the brute force approach using extra space is straightforward and efficient with O(n) time complexity, the optimized in-place solution shows how we can solve the problem without additional memory.
The cycle-following technique used in the optimized approach is a valuable pattern that appears in other array manipulation problems too. By marking processed elements and carefully tracking our position in the array, we can achieve an in-place solution.
