See the original problem on HackerRank.
Bob has an array \( a \) with \( n \) positive integer elements. Bob likes order, so he wants his array to be sorted in nondecreasing order. He decides to swap two elements in the array to make his array sorted. (A swap is defined as switching two elements at distinct locations in the array.) Your task is to determine if this can be done.
 If he can't sort the array with one swap, print \( 1 \).
 If the array is already sorted, print \( 0 \).
 If he can sort the array with one swap, print \( 1 \).
Input Format
The first line contains a single integer \( n \).
The second line contains \( n \) spaceseparated integers \( a_1, a_2, …, a_n \), the elements of the array \( a \).
Constraints
 \( 1 \leq n \leq 10^3 \)
 \( 1 \leq a_i \leq 10^9 \)
Output Format
Print a single line containing an integer denoting the answer. This should be either \( 1 \), \( 0 \), or \( 1 \).
Solutions
Since the input space is quite small, a cubic solutions works: first of all, we check if the array is sorted. If so, we print 0. Otherwise, we try swapping every pair of indices and check if the array become sorted along the way.
Simple implementation of this idea in Python:


Clearly this is an inefficient solution!
We could do better and solve the problem in linear time.
Linear Solution
It's very important to see that we have only one possible swap  as the title suggests!
Instead of swapping every possible pair, we should focus only on the first one that breaks the order.
Let's start from this simple example:
We first find the first element making the array unsorted  the first number bigger than the following one:
10 is one of the two elements to swap. The other is simply the first element smaller than 10, searching from the end of the array:
We don't have other choices, since we can only do one swap.
Here is the implementation of this idea in C++  note that we don't use explicit loops because the standard library provides all the algorhtms we need:


is_sorted_until
finds the first element breaking the order. If this element does not exist (or we have only one element), the sequence is sorted and we print 0.
Otherwise, we need to find the first element smaller than the one found at the previous step. We use find_if
with reverse iterators, to search backwards.
It's interesting to note here: it's impossible not to find such an element because the array is not sorted! In the worst case, we just find the element following the one breaking the order (it would be 5, in the example above).
Finally, we swap and check if the array becomes sorted (we can start checking from it
because we know the previous part is sorted). If so we print 1, otherwise we print 1.
Minor C++ detail: we convert the reverse iterator to a normal iterator with .base()
but we also need to step it back by one position because the base (standard) iterator refers to the element that is next to the element the reverse_iterator
is currently pointing to. See here for more details.
Alternative solution
We find the first bad pair (l, r). When found, we find the next bad pair (l1, r1) and swap l with r1. Special cases: no bad pair found (result=0) or no second bad pair found (swap l with r). If a second (l, r) bad pair is found, result is 1.
This solution is linear and actually swaps elements, so the resulting list is sorted.


Sort
We can sort the input array, then count the mismatching items.


If there are more than 2 two mismatching items, we need more than one swap to
sort the list, so the answer is 1
.

