Fewest Swaps to Order a Permutation
MediumArrays & Hashing
Problem
A shelf holds n books whose catalogue numbers are a permutation of 0..n-1, stored in shelf. A librarian may swap any two books in one move.
Return the minimum number of swaps needed to make shelf[i] = i for every i.
Example 1
- Input:
- shelf = [2, 0, 1]
- Output:
- 2
Swap slots 0 and 2 → [1, 0, 2], then slots 0 and 1 → [0, 1, 2].
Example 2
- Input:
- shelf = [1, 0, 3, 2]
- Output:
- 2
Example 3
- Input:
- shelf = [0, 1, 2]
- Output:
- 0
Constraints
- 1 ≤ n ≤ 10^5
- shelf is a permutation of 0..n-1.
Hint
Show the first hint
Draw an arrow from each slot i to the slot where its book belongs, shelf[i]. What shapes appear?
Walkthrough
How to approach it
01Clarify before coding
- Any two books, not only neighbours? Yes, arbitrary swaps.
- Is it a true permutation of 0..n-1? Yes, so every book has exactly one home slot.
- May I modify the array? Yes; otherwise use a visited marker per cycle.
02Brute force
Breadth-first search over arrangements, where each move is a swap, until the sorted arrangement is reached.
Cost: Up to n! states: infeasible beyond tiny n.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.