Minimum number of swaps to sort an array

Medium

Problem

The array holds distinct values. Return the minimum number of swaps (of any two elements) needed to sort it.

Example 1

Input:  [2, 8, 5, 4]
Output: 1

Swap 8 and 4.

Example 2

Input:  [10, 19, 6, 3, 5]
Output: 2

Also asked as: minimum no. of swaps required to sort the array

Test cases

Case 1

Input:    [2,8,5,4]
Expected: 1

Case 2

Input:    [10,19,6,3,5]
Expected: 2

Case 3

Input:    [4,3,2,1]
Expected: 2

Case 4

Input:    [1,2,3]
Expected: 0

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Cycle decomposition

Time O(n log n)Space O(n)

Pair each value with its target index; the permutation splits into cycles. A cycle of length L needs L−1 swaps.

function minSwaps(a) {
const sorted = a.map((v, i) => [v, i]).sort((x, y) => x[0] - y[0]);
const seen = Array(a.length).fill(false);
let swaps = 0;
for (let i = 0; i < a.length; i++) {
if (seen[i] || sorted[i][1] === i) continue;
let len = 0, j = i;
while (!seen[j]) { seen[j] = true; j = sorted[j][1]; len++; }
swaps += len - 1;
}
return swaps;
}