Fewest Swaps to Sort
All items of nums are different. One move swaps two items, which do not have to be next to each other.
Return the fewest moves that put nums in increasing order. A list that is already in order, an empty one included, needs 0.
Example 1
nums [4,3,2,1]
returns 2
Swap 4 with 1, then 3 with 2. No single swap sorts it.
Example 2
nums [2,3,1]
returns 2
The three items go round in a circle: swap 2 with 1, then 3 with 2 (or any two swaps that walk the circle).
Constraints
0 <= len(nums) <= 100-1000 <= nums[i] <= 1000- all items are different
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Arrays problems
- Insert IntervalMedium
- Longest HillMedium
- Maximum SubarrayMedium
- Next PermutationMedium
- Nudge Every ItemMedium
- Product of Array Except SelfMedium
- Range IncrementsMedium
- Rising TripleMedium