270. One Swap Away
Core1000 ms256 MBSolved by 0%
Print Yes if the array is already sorted in non-decreasing order, or can be
made sorted by swapping exactly one pair of positions. Print No otherwise.
Compare the array with its sorted version. The positions where they disagree are the only ones a swap could fix.
If there are no such positions it is already sorted. If there are exactly two, one swap might work, and you must check that it actually does. Any other count cannot be fixed by a single swap.
Constraints - `1 ≤ n ≤ 200000` - `-1000000000 ≤ a[i] ≤ 1000000000`
Input
The first line contains an integer n.
The second line contains n integers.
Output
Print Yes or No on one line.
Input4
1 3 2 4
OutputYes
Notehas exactly one pair out of place
Input4
4 3 2 1
OutputNo
Notehas four positions wrong, which one swap cannot fix
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.
Hint 1Where to start
Hint 2The approachOpen hint 1 first. This one carries on from it.
Hint 3PseudocodeOpen hint 2 first. This one carries on from it.
Hint 4Full solutionOpen hint 3 first. This one carries on from it.