How far from sorted?
Compare against the sorted version to see what's really out of place. About 9 minutes.
Compare against the sorted version
Build the sorted version of the list, with any sort you like, and lay it next to the original. Go position by position. Wherever they agree, the value is already where it belongs, like a student already in the right seat.
The positions where they disagree are exactly what's out of place.
Index 1 (5 vs 2) and index 4 (2 vs 5) disagree with the sorted version. Everywhere else matches.
Zero mismatches, or exactly two that trade
No mismatches means the list is already sorted. If there are exactly two, swapping those two positions must fix them, provided each one holds the value the other needs. Any other number of mismatches can't be fixed with one swap, since a swap only ever changes two positions.
target = sorted(nums)
diff = []
for i in range(len(nums)):
if nums[i] != target[i]:
diff.append(i)
if len(diff) == 0:
return True
if len(diff) != 2:
return False
a, b = diff
return (nums[a] == target[b]
and nums[b] == target[a])nums = [3, 2, 1]. Is nums sorted, or one swap away from sorted?
- AYes — swap index 0 and 2
- BNo — it's fully reversed, so one swap can't be enough
- CYes — swap index 0 and 1
Show the answer
Yes — swap index 0 and 2. Only index 0 (3 vs 1) and index 2 (1 vs 3) disagree with the sorted version [1, 2, 3]; index 1 already matches.
One swap from sorted
Return true if nums is already sorted from smallest to largest, or if swapping the values at exactly two positions (anywhere in nums, not just neighbours) would make it sorted. Otherwise return false.
nums = [1, 5, 3, 4, 2] → true
0 ≤ n ≤ 100,000 · −1,000,000,000 ≤ each value ≤ 1,000,000,000