One Swap

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 \).

Input Format

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 \).

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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

n = input()
a = map(int, input().split())

def is_sorted():
    return all(a[i] <= a[i + 1] for i in range(n - 1))

def solve():
    if is_sorted():
        return 0
    for i in range(n):
        for j in range(i):
            a[i], a[j] = a[j], a[i]
            if is_sorted():
                return 1
            a[i], a[j] = a[j], a[i]
    return -1

print(solve())

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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

int N; cin >> N;
vector<int> a(N);
copy_n(istream_iterator<int>(cin), N, begin(a));

auto it = is_sorted_until(begin(a), end(a));
if (it == end(a)) {
    cout << 0;
}
else if (a.size() == 1)
{
    cout << 1;
}
else
{
    auto lb = *prev(it);
    auto targetRev = find_if(rbegin(a), make_reverse_iterator(it), [=](auto i){
        return i < lb;
    });
    auto target = prev(targetRev.base());
    iter_swap(prev(it), target);
    cout << (is_sorted(it, end(a)) ? 1 : -1);
}

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

int one_swap(std::vector<int> v) {
    int result = 0;

    /* Find the first pair where left is greater than right */
    auto l = std::begin(v);
    auto r = std::next(l);

    for (; r < std::end(v); ++l, ++r) {
        if (*l > *r) {
            /* Bad pair found.
             * We can do something only if this is the first found. */
            if (result == 1) return -1;

            auto l1 = std::next(r);
            auto r1 = std::next(l1);

            /* Find the next bad pair */
            for (; r1 < std::end(v); ++l1, ++r1) {
                if (*l1 > *r1) {
                    /* Bad pair found, swap! */
                    std::swap(*l, *r1);
                    result = 1;
                    break;
                }
            }

            /* No other bad pair, we can swap this */
            if (r1 == std::end(v)) {
                std::swap(*l, *r);
                result = 1;
            }
        }
    }

    return result;
}

Sort

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 -1.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

import Data.List (sort)

answer 0 = 0
answer 1 = 1
answer 2 = 1
answer _ = -1

countMismatches xs ys =
  foldl fn 0 $ zip xs ys
  where
    fn c (a, s) = if a == s then c + 1 else c

main = do
  _ <- getLine
  input <- getLine
  let arr = ((fmap read) . words) input :: [Int]
  let sorted = sort arr
  print $ answer $ length arr - countMismatches arr sorted