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 <= 1000001 <= arr[i] <= 1000000All values in arr are distinct.
Hints for Minimum Swaps to Sort
Hint 1
Think of each element as needing to move to the position it occupies once sorted. That defines a permutation.
Hint 2
A permutation decomposes into disjoint cycles, and cycles are independent of each other.
Hint 3
A cycle of length
Lcosts exactlyL - 1swaps. 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
- Build
idx, the indices0..n-1sorted by their value inarr.idx[i]is the original position of the element that belongs at positioni. - Walk every unvisited
i, followingj = idx[j]and marking visited, to measure that cycle's length. - Add
length - 1to 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 swapsJava
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