Introduction

Rearranging an array by an indices array means applying a permutation. Usually, the rule is that indices[i] tells you the destination position of arr[i]. The simplest solution uses a second array, while the more interesting version applies the permutation in place by following cycles.

Clarify the Meaning of the Indices Array

Suppose:

• data array is ['A', 'B', 'C', 'D']
• indices array is [2, 0, 1, 3]

That means:

• ''A' moves to index 2'
• ''B' moves to index 0'
• ''C' moves to index 1'
• ''D' stays at index 3'

So the final array is:

['B', 'C', 'A', 'D']

This interpretation matters because some problems define the index array in the opposite direction. Always verify whether the indices represent source positions or destination positions.

The Easiest Solution: Use an Extra Array

The clearest approach is to build a result array of the same size and place each element into its target position.

1def rearrange_with_extra_space(arr, indices):
2    if len(arr) != len(indices):
3        raise ValueError("arr and indices must have the same length")
4
5    result = [None] * len(arr)
6    for i, value in enumerate(arr):
7        result[indices[i]] = value
8    return result
9
10
11arr = ["A", "B", "C", "D"]
12indices = [2, 0, 1, 3]
13print(rearrange_with_extra_space(arr, indices))

This runs in O(n) time and uses O(n) extra space. For most applications, it is the best balance of simplicity and reliability.

Validate the Indices First

A valid permutation of length n must contain every value from 0 through n - 1 exactly once. If the indices array contains duplicates or out-of-range values, the rearrangement is invalid.

1def is_valid_permutation(indices):
2    n = len(indices)
3    return sorted(indices) == list(range(n))
4
5
6print(is_valid_permutation([2, 0, 1, 3]))
7print(is_valid_permutation([2, 2, 1, 3]))

This check is useful because otherwise elements may be overwritten or positions may never be filled.

In-Place Rearrangement With Cycles

If extra memory matters, you can apply the permutation in place. The idea is to follow cycles in the mapping and swap until each element reaches its final position.

1def rearrange_in_place(arr, indices):
2    if len(arr) != len(indices):
3        raise ValueError("arr and indices must have the same length")
4    if sorted(indices) != list(range(len(indices))):
5        raise ValueError("indices must be a valid permutation")
6
7    for i in range(len(arr)):
8        while indices[i] != i:
9            target = indices[i]
10            arr[i], arr[target] = arr[target], arr[i]
11            indices[i], indices[target] = indices[target], indices[i]
12
13    return arr
14
15
16arr = ["A", "B", "C", "D"]
17indices = [2, 0, 1, 3]
18print(rearrange_in_place(arr, indices))

Notice that this mutates both arr and indices. That is common in in-place solutions because the index array itself is used as part of the bookkeeping.

Why the In-Place Version Works

A permutation is made of cycles. In the example [2, 0, 1, 3], the first three positions form one cycle:

• '0 -> 2'
• '2 -> 1'
• '1 -> 0'

The in-place algorithm keeps swapping until each cycle collapses into the identity mapping, meaning indices[i] == i for every position.

That is why the loop condition checks whether the current element is already in its final location.

When to Choose Which Approach

Use the extra-array solution when:

• clarity matters most
• memory is not tight
• you want to keep the original indices unchanged

Use the in-place solution when:

• auxiliary memory matters
• mutating the index array is acceptable
• the permutation property is guaranteed or validated

In production code, the extra-array version is often preferable because it is much easier to read and debug.

Common Pitfalls

The biggest mistake is misunderstanding what indices[i] means. If the problem defines it as a source position and you treat it as a destination, the result will be wrong even though the code looks reasonable.

Another mistake is skipping validation. Duplicate or out-of-range indices make the permutation invalid and can silently corrupt the output.

People also forget that the in-place algorithm usually mutates the indices array. If the caller needs to keep the original indices, pass a copy.

Finally, do not use the in-place version just because it looks clever. If extra space is acceptable, the direct construction approach is often better.

Summary

• Rearranging by an indices array is an application of a permutation.
• The simplest solution builds a new array and places each element in its target position.
• A valid indices array must be a true permutation of 0 through n - 1.
• In-place rearrangement works by following permutation cycles.
• Choose the simpler extra-array version unless memory constraints really justify the in-place approach.