Minimum Swaps to Sort — Medium Problem & Solution

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.

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

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Minimum Number of Increments on Subarrays to Form a Target Array Medium
• Find the Winner of an Array Game Medium
• Queries on a Permutation With Key Medium
• Corporate Flight Bookings Medium
• Find the Winner of the Circular Game Medium
• Longest Subsequence With Limited Sum Medium