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 displacementrightmost = [1, -1]        # The second the index where it occurredfor 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] = ireturn 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.
Minimizing inversions in an array with a single swap
algorithms;optimization;correctness proof;permutations