Minimum Swaps to Sort

Medium
610.

Minimum Swaps to Sort

Minimum Swaps to Sort is a medium coding problem on arrays, sorting and graph, asked in Amazon, Adobe and Morgan Stanley interviews.

Given an array arr of distinct integers, return the minimum number of swaps needed to sort it in ascending order. A swap may exchange any two positions, not just adjacent ones.

Example 1

Input
arr = [2,8,5,4]
Output
1
Explanation
Swapping 8 and 4 gives [2,4,5,8].

Example 2

Input
arr = [10,19,6,3,5]
Output
2
Explanation
Swap 10 with 3, then 19 with 5.

Example 3

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

Constraints

  • 1 <= arr.length <= 100000
  • 1 <= arr[i] <= 1000000
  • All values in arr are distinct.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @return {number}
 */
var minSwaps = function(arr) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Swaps to Sort — Solution in Python, Java & C++

Minimum Swaps to Sort solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Minimum Swaps to Sort is a medium coding problem on arrays, sorting and graph, asked in Amazon, Adobe and Morgan Stanley interviews.

  • Difficulty: Medium
  • Topics: Arrays, Sorting, Graph
  • Asked at: Amazon, Adobe, Morgan Stanley
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given an array arr of distinct integers, return the minimum number of swaps needed to sort it in ascending order. A swap may exchange any two positions, not just adjacent ones.

Example 1

Input: arr = [2,8,5,4]
Output: 1
Explanation: Swapping 8 and 4 gives [2,4,5,8].

Example 2

Input: arr = [10,19,6,3,5]
Output: 2
Explanation: Swap 10 with 3, then 19 with 5.

Example 3

Input: arr = [1,2,3]
Output: 0

Constraints

  • 1 <= arr.length <= 100000
  • 1 <= arr[i] <= 1000000
  • All values in arr are distinct.

Hints for Minimum Swaps to Sort

  1. Hint 1

    Think of each element as needing to move to the position it occupies once sorted. That defines a permutation.

  2. Hint 2

    A permutation decomposes into disjoint cycles, and cycles are independent of each other.

  3. Hint 3

    A cycle of length L costs exactly L - 1 swaps. Sum over all cycles.

How to solve Minimum Swaps to Sort

Sorting is a permutation: element at position i must end up at the index it takes in sorted order. A permutation splits into disjoint cycles, and a cycle of length L needs exactly L - 1 swaps — so the answer is n minus the number of cycles.

Approach

  1. Build idx, the indices 0..n-1 sorted by their value in arr. idx[i] is the original position of the element that belongs at position i.
  2. Walk every unvisited i, following j = idx[j] and marking visited, to measure that cycle's length.
  3. Add length - 1 to the answer for each cycle.

Why it works

Within one cycle no element is already home, and each swap can place at most one element correctly while keeping the rest a cycle, so L - 1 swaps are both necessary and sufficient. Distinct cycles share no positions, so their costs simply add.

Complexity

  • Time — O(n log n) for the sort
  • Space — O(n)

Pitfalls

  • Fixed points (idx[i] == i) are cycles of length 1 and cost nothing — counting them as 1 swap inflates the answer.
  • The technique assumes distinct values; with duplicates the target permutation is no longer unique.

Reference solution

Python

from typing import List

def minSwaps(arr: List[int]) -> int:
    n = len(arr)
    idx = sorted(range(n), key=lambda i: arr[i])
    done = [False] * n
    swaps = 0
    for i in range(n):
        if done[i] or idx[i] == i:
            continue
        size = 0
        j = i
        while not done[j]:
            done[j] = True
            j = idx[j]
            size += 1
        swaps += size - 1
    return swaps

Java

public static int minSwaps(int[] arr) {
    int n = arr.length;
    Integer[] order = new Integer[n];
    for (int i = 0; i < n; i++) order[i] = i;
    Arrays.sort(order, (a, b) -> Integer.compare(arr[a], arr[b]));
    boolean[] done = new boolean[n];
    int swaps = 0;
    for (int i = 0; i < n; i++) {
        if (done[i] || order[i] == i) continue;
        int size = 0, j = i;
        while (!done[j]) { done[j] = true; j = order[j]; size++; }
        swaps += size - 1;
    }
    return swaps;
}

C++

int minSwaps(vector<int>& arr) {
    int n = (int) arr.size();
    vector<int> idx(n);
    for (int i = 0; i < n; i++) idx[i] = i;
    sort(idx.begin(), idx.end(), [&](int a, int b) { return arr[a] < arr[b]; });
    vector<bool> done(n, false);
    int swaps = 0;
    for (int i = 0; i < n; i++) {
        if (done[i] || idx[i] == i) continue;
        int size = 0, j = i;
        while (!done[j]) { done[j] = true; j = idx[j]; size++; }
        swaps += size - 1;
    }
    return swaps;
}

JavaScript

var minSwaps = function(arr) {
    var n = arr.length;
    var idx = [];
    for (var t = 0; t < n; t++) idx.push(t);
    idx.sort(function(a, b) { return arr[a] - arr[b]; });
    var done = [];
    for (var u = 0; u < n; u++) done.push(false);
    var swaps = 0;
    for (var i = 0; i < n; i++) {
        if (done[i] || idx[i] === i) continue;
        var size = 0, j = i;
        while (!done[j]) { done[j] = true; j = idx[j]; size++; }
        swaps += size - 1;
    }
    return swaps;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms