Minimum swaps to sort an array Hard 0 attempts
GeeksforGeeks ↗

Minimum swaps to sort an array

Hard Sorting&Searching GeeksforGeeks

Given an array of N distinct elements, find the minimum number of swaps to sort it.

Example: arr = [4,3,2,1] → Output: 2

Sample Input
—
Sample Output
—
Constraints
  • 1 <= N <= 10^5
  • 1 <= arr[i] <= 10^6
Topics
Sorting&Searching

Cycle Detection

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