Minimizing inversions in an array with a single swap 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 &lt; j$ but 
  $a[i] &gt; 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 &gt; leftmost[0]
        leftmost[0] = d
        leftmost[1] = i
    else if d &lt; 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.
Let's calculate the difference in number of inversions given that you swap $a_i$ and $a_j$. We can assume that $i &lt; 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 &lt; k &lt; j$, $(i,k)$ and $(k,j)$. We can distinguish two cases: $a_i &lt; a_j$ and $a_i &gt; a_j$.

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


$a_k &lt; a_i &lt; a_j$: number of inversions stays the same.
$a_i &lt; a_j &lt; a_k$: number of inversions stays the same.
$a_i &lt; a_k &lt; 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 &lt; a_i$ then the number of inversions decreases by one plus twice the number of indices $i &lt; k &lt; j$ such that $a_j &lt; a_k &lt; 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 &lt; a_i$ and the number of indices $i &lt; k &lt; j$ satisfying $a_j &lt; a_k &lt; a_i$ is maximal. You take it from here.