Coding Interview PatternsMinimum Swaps to Sort
MediumCyclic Sort
Minimum Swaps to Sort
Explanation & Solution
Description
Given an array of n distinct integers, find the minimum number of swaps required to sort the array in ascending order.
A swap exchanges any two elements in the array (not necessarily adjacent).
Input:nums = [2, 3, 1]
0
2
1
3
2
1
Output: 2
Explanation: Swap 2 and 1 → [1, 3, 2], then swap 3 and 2 → [1, 2, 3]. Total: 2 swaps.
Constraints
1 <= nums.length <= 10^5- All elements of
numsare distinct 1 <= nums[i] <= 10^6
Approach
Cyclic Sort pattern
1. Build a Position Map
- Sort a copy of the array to get the target order
- Create a map from each value to its target index in the sorted array
2. Decompose the Permutation into Cycles
- Think of the current array as a permutation: element at index
ibelongs at indexposMap[nums[i]] - Starting from any unvisited index
i, follow the chaini → posMap[nums[i]] → ...until you revisiti - This forms a cycle in the permutation
3. Minimum Swaps per Cycle
- A cycle of length
Lcan be sorted using exactlyL - 1swaps - A cycle of length 1 (element already in place) requires 0 swaps
- Sum
(cycleLen - 1)over all cycles to get the total minimum swaps
4. Why Cycles Work
- Any permutation decomposes uniquely into disjoint cycles
- To sort a cycle, you can rotate elements one position at a time, each rotation being one swap
- A cycle of length L requires exactly L - 1 rotations (swaps)
🧠 Key Insight
- This is the cyclic sort perspective applied in reverse: instead of performing the swaps, we count how many a cyclic decomposition would require. The minimum total swaps equals n minus the number of cycles in the permutation
Time
O(n log n)dominated by sorting; cycle traversal is O(n)Space
O(n)for the position map and visited arrayVisualization
Input:
[2, 3, 1]
—
Press ▶ or use ← → to step through
Pointer iPointer jProcessedDone
6 steps