Introduction

To compute the minimum swaps needed to transform one array into another, you first need to define what kind of swap is allowed. If any two positions may be swapped, the answer comes from cycle decomposition. If only adjacent swaps are allowed, the answer is different and is based on inversion counting after remapping the first array into the target order.

Case 1: Arbitrary Swaps

Assume both arrays contain the same unique values, and you may swap any two positions.

Example:

• array 1: [4, 3, 2, 1]
• array 2: [1, 3, 4, 2]

Map each value in the target array to its index:

target_index = {1: 0, 3: 1, 4: 2, 2: 3}

Now convert array 1 into the permutation of target positions:

perm = [2, 1, 3, 0]

The minimum number of arbitrary swaps is the sum of:

cycle_length - 1

for each cycle in that permutation.

Python Implementation for Arbitrary Swaps

1def min_swaps_any_positions(a, b):
2    if sorted(a) != sorted(b):
3        raise ValueError("Arrays must contain the same elements")
4
5    target_index = {value: i for i, value in enumerate(b)}
6    perm = [target_index[value] for value in a]
7
8    visited = [False] * len(perm)
9    swaps = 0
10
11    for i in range(len(perm)):
12        if visited[i] or perm[i] == i:
13            continue
14
15        cycle_len = 0
16        j = i
17        while not visited[j]:
18            visited[j] = True
19            j = perm[j]
20            cycle_len += 1
21
22        swaps += cycle_len - 1
23
24    return swaps
25
26
27print(min_swaps_any_positions([4, 3, 2, 1], [1, 3, 4, 2]))

This runs in linear time once the target-position map is built.

Case 2: Adjacent Swaps

If the problem means adjacent swaps only, the cycle method is no longer correct. Now the answer is the number of inversions in the remapped position array.

Using the same remapped permutation:

perm = [2, 1, 3, 0]

The number of inversions in that sequence equals the minimum number of adjacent swaps needed.

A simple but slower implementation is:

1def min_adjacent_swaps(a, b):
2    if sorted(a) != sorted(b):
3        raise ValueError("Arrays must contain the same elements")
4
5    target_index = {value: i for i, value in enumerate(b)}
6    perm = [target_index[value] for value in a]
7
8    inversions = 0
9    for i in range(len(perm)):
10        for j in range(i + 1, len(perm)):
11            if perm[i] > perm[j]:
12                inversions += 1
13
14    return inversions
15
16
17print(min_adjacent_swaps([4, 3, 2, 1], [1, 3, 4, 2]))

For large arrays, replace the nested loops with a Fenwick tree or merge-sort inversion counter to get O(n log n) time.

Why the Distinction Matters

These are different optimization problems:

• arbitrary swaps minimize how many pair exchanges you perform
• adjacent swaps minimize how many local moves you perform

For the same two arrays, the answers can differ. That is why the problem statement must be precise before choosing an algorithm.

Common Pitfalls

The most common mistake is applying the cycle-decomposition formula when the problem really means adjacent swaps. That gives the wrong answer because adjacent swaps are more restrictive.

Another issue is assuming the arrays are valid permutations of each other without checking. If the arrays do not contain the same multiset of elements, the transformation is impossible.

A third pitfall is ignoring duplicates. The simple mapping approach shown here assumes unique values. If duplicates exist, you need a more careful position-matching strategy.

Finally, do not overcomplicate the arbitrary-swap case. Once the arrays are remapped to a permutation, the cycle logic is the cleanest answer.

Summary

• First decide whether swaps can happen anywhere or only between adjacent elements.
• For arbitrary swaps, use cycle decomposition on the remapped permutation.
• For adjacent swaps, count inversions in the remapped permutation.
• The arrays must contain the same elements to make the transformation possible.
• Duplicate values require extra care beyond the simple unique-element mapping shown here.