Minimizing inversions in an array with a single swap

Question

This was asked in the (very) recently concluded Hackerrank Worldcup. Paraphrased:

Given a permutation $a$ of integers from $1$ to $N$, how can I minimize the number of inversions by a single swap of any two integers?

An inversion is a pair of indices $(i, j)$ such that $i < j$ but $a[i] > a[j]$.

I think that this can be achieved by swapping the numbers which have been shifted the most from their position. That is:

If $n_{inv}(a)$ is the number of inversions in a permutation $a$, and $swap_a(i, j)$ is the permutation obtained by swapping the integers at $i$, $j$, then:

$$ \underset{i, j}{argmin} \{n_{inv}(swap_a(i, j))\} = \underset{i}{argmax} (a[i] -i), \underset{j}{argmin} (a[j] - j) $$

In pseudo-code:

leftmost = [-1, -1]        # The first value is the displacement
rightmost = [1, -1]        # The second the index where it occurred
for i in 1..n
    d = N[i] - i           # N being the array of numbers
    if d > leftmost[0]
        leftmost[0] = d
        leftmost[1] = i
    else if d < rightmost[0]
        rightmost[0] = d
        rightmost[1] = i
return leftmost[1], rightmost[1]

---

The thing is, I have no idea why this is correct, or even if it is. How can I prove that this works? Or determine the conditions for which it will work?

---

I have been struggling to understand how I reached this idea and feel that proving it would help me.

To be clear, I am not looking for a solution to the minimizing inversions problem, but only a way to prove that the solution I came up with is correct or incorrect.

Answer 1

Let's calculate the difference in number of inversions given that you swap $a_i$ and $a_j$. We can assume that $i < j$. There are three kinds of pairs of indices whose status (being inversions or not) could change as a result of the swap: $(i,j)$ and, for $i < k < j$, $(i,k)$ and $(k,j)$. We can distinguish two cases: $a_i < a_j$ and $a_i > a_j$.

If $a_i < a_j$ then the pair $(i,j)$ becomes an inversion, and for every $i < k < j$, there are three possible cases:

1. $a_k < a_i < a_j$: number of inversions stays the same.

2. $a_i < a_j < a_k$: number of inversions stays the same.

3. $a_i < a_k < a_j$: number of inversions increases by 2.

This is clearly not a good idea if you can avoid it. If you must (when the permutation is monotone increasing), it's best to switch a pair $a_i,a_{i+1}$.

In contrast, if $a_j < a_i$ then the number of inversions decreases by one plus twice the number of indices $i < k < j$ such that $a_j < a_k < a_i$. As a consequence, if the permutation is not monotone increasing, your goal is to choose a pair $(i,j)$ such that $a_j < a_i$ and the number of indices $i < k < j$ satisfying $a_j < a_k < a_i$ is maximal. You take it from here.