Minimum Swaps to Sort — Solution & Editorial

Back to the Problem

Decompose the permutation into cycles; a cycle of length L needs L−1 swaps, so the answer is N minus the number of cycles.

Complexity: O(N)