Fewest Swaps to Sort
Problem
Given a list of distinct integers, return the smallest number of swaps that sorts it in ascending order. One swap exchanges the values at any two positions, and the two positions do not have to be next to each other.
Examples
Input: nums = [4, 3, 1, 2]
Output: 3
Why: 4 must go to index 3, the 2 there to index 1, the 3 there to
index 2 and the 1 there to index 0: one loop of four valuesInput: nums = [10, 30, 20]
Output: 1
Why: swapping 30 and 20 is enoughInput: nums = [7]
Output: 0
Why: edge case, a single value is already sortedHints
0 / 3
Look at where each value has to go. Following a value to its target position, then the value sitting there to its own target, and so on, eventually brings you back to the start.
Those loops are independent of each other. One swap can put a value into its final position and shrink its loop by one, and no swap can do better than splitting one loop into two.
Map every value to its index in the sorted list, then walk each loop once, marking positions as visited. A loop of length L needs L - 1 swaps; add those up.
Solution
Sending each value to its sorted position splits the positions into cycles, and a sorted list is exactly n cycles of length one. Any swap changes the number of cycles by exactly one, so at least n minus the current cycle count swaps are needed, and placing one value into its final position per swap achieves that: a cycle of length L costs L - 1. Selection sort that skips swapping a value with itself follows exactly this plan, which is why it never makes more swaps than necessary even though it makes O(n²) comparisons. Time is O(n log n) for the sort that finds the targets, and space is O(n).
def fewest_swaps(nums):
target = {v: i for i, v in enumerate(sorted(nums))} # where each value belongs
seen, swaps = [False] * len(nums), 0
for start in range(len(nums)):
length, i = 0, start
while not seen[i]: # walk one cycle back to its start
seen[i] = True
i = target[nums[i]]
length += 1
swaps += max(length - 1, 0) # a cycle of L values needs L - 1 swaps
return swaps
print(fewest_swaps([4, 3, 1, 2])) # -> 3
print(fewest_swaps([10, 30, 20])) # -> 1
print(fewest_swaps([7])) # -> 0Stuck on the idea rather than the code? Selection Sort covers it.