Minimum swaps to sort an array Hard 0 attempts
GeeksforGeeks ↗

Minimum swaps to sort an array

Hard Sorting&Searching GeeksforGeeks

You're given an array of N distinct values. Using swaps that exchange any two elements, determine the fewest swaps needed to arrange the array in ascending order.

Input Format
Implement minSwaps(arr). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 ยท Run Sample

Input
arr = [4,3,2,1]
Output
2

Example 2

Input
arr = [1,2,3]
Output
0
Constraints
  • 1 <= arr.length <= 10^5
  • 1 <= arr[i] <= 10^6
  • All values are distinct.
Test Cases (2)
Case 1
Args: [[4,3,2,1]] Expected: 2
Case 2
Args: [[1,2,3]] Expected: 0
Topics
Sorting&Searching

Cycle Detection

javascript
function minSwaps(arr) {
  const sorted = [...arr].sort((a,b)=>a-b);
  const idx = new Map(); arr.forEach((v,i)=>idx.set(v,i));
  const visited = Array(arr.length).fill(false);
  let swaps = 0;
  for (let i = 0; i < arr.length; i++) {
    if (visited[i] || arr[i]===sorted[i]) continue;
    let cycleLen = 0, j = i;
    while (!visited[j]) { visited[j]=true; j=idx.get(sorted[j]); cycleLen++; }
    swaps += cycleLen - 1;
  }
  return swaps;
}

Time: O(n log n) | Space: O(n)

Saved in this browser only. Private to you.

JavaScript