One Swap Away — Solution & Editorial

Back to the Problem

Compare with the sorted copy: zero mismatching positions means already sorted; exactly two means test that one swap; anything else is impossible.

Complexity: O(N log N)

Watch out: Duplicates make 'find the two bad positions by scanning' fragile — comparing against the sorted array is robust.