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 non-decreasing 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 \).
The first line contains a single integer \( n \).
The second line contains \( n \) space-separated integers \( a_1, a_2, …, a_n \), the elements of the array \( a \).
- \( 1 \leq n \leq 10^3 \)
- \( 1 \leq a_i \leq 10^9 \)
Print a single line containing an integer denoting the answer. This should be either \( -1 \), \( 0 \), or \( 1 \).
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.
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.
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.
We can sort the input array, then count the mismatching items.
1 2 3
original: 1 10 3 4 3 sorted: 1 3 3 4 10 diff: _ + _ _ + -> 2 mismatching
If there are more than 2 two mismatching items, we need more than one swap to
sort the list, so the answer is