Minimum number of swaps to sort an array
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
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;}