The problem goes like this:
Given two arrays of same size, we need to convert the first array into another with minimum operations. In an operation, we can either increment or decrement an element by one. Note that orders of appearance of elements do not need to be same.
Here, to convert one number into another we can add or subtract 1 from it.
Examples:
Input: $a = \{ 3, 1, 1 \}, b = \{ 1, 2, 2 \}$
Output: $2$
Explanation:
Here we can increase any $1$ into $2$ by $1$ operation and $3$ to $2$ in one decrement operation, so a[] becomes $\{2, 2, 1\}$ which is a permutation of b[].
Input: $a = \{ 3, 1, 1 \}, b = \{ 1, 1, 2 \}$
Output: $1$
It has been nicely explained with example and working code here. The gist is to first sort both array and then take element wise difference, which when added gives the correct answer.
Is there any mathematical proof of why this process works? Why do we need to sort the values first?
Thanks.
This is a combinatorial optimization problem: $$\min_{\pi \in S_n}{\sum_{i=1}^{n}{|a_i-b_{\pi(i)}|}}$$ Where $S = \{1,2,...,n\}$ is the set of indices, and $S_n$ is the set of all permutations of $S$, $\pi$ being a permutation ($\pi : S \rightarrow S$). That is, this gives the minimal number of operations necessary to turn the array $a$ into the array $b$ ($|a|=|b|$), where we consider an increment/decrement by $1$ to be one operation. In general problems of this sort are quite hard to optimize, but it happens that for this specific problem there is a nice and easy solution (outlined by the algorithm you linked).
I have no idea how they arrived at the solution beyond guessing it (maybe somebody else would be able to clarify this), but I believe that I can prove that the solution in the algorithm is the optimal such.
Let us consider the sorted arrays, that is: $a_1\leq a_2\leq ...\leq a_n$; $b_1\leq b_2\leq...\leq b_n$. Then the number of operations is given by $\sum_{i=1}^{n}{|a_i-b_i|}$. I'll show that if I swap the places of any 2 elements in the solution I cannot get a smaller number of operations (meaning that what we have will be the minimum and thus optimal). Let $j,k \in S$ be arbitrary such that $j\ne k$, without loss of generality we can choose $j<k$. We will swap their places in the solution and look at the difference between the number of operations of the solution proposed by the algorithm and the one resulting from the swap. We want to prove that: $$\sum_{i=1}^{n}{|a_i-b_i|} \leq \sum_{i=1}^{j-1}{|a_i-b_i|} + |a_j-b_k| + \sum_{i=j+1}^{k-1}{|a_i-b_i|} + |a_k-b_j| + \sum_{i=k+1}^{n}{|a_i-b_i|}$$ Where I use the convention that a sum over an empty interval is $0$. After I subtract the left hand side from the right hand side of the inequality I get:
$$0 \leq |a_j-b_k| + |a_k-b_j| - |a_j-b_j| - |a_k-b_k|$$
Let's consider all possible cases:
$$1) \quad a_j < a_k \leq b_j < b_k$$ $$0\leq |a_j-b_k| + |a_k-b_j| - |a_j-b_j| - |a_k-b_k| = b_k-a_j + b_j-a_k - b_j+ a_j - b_k + a_k = 0$$ Thus the equality is satisfied in the first case (which means that we have the optimal solution but in general we won't have to sort if $\max_{i\in S}{a_i}\leq \min_{i \in S}{b_i}$ and we can just assign arbitrary indices, note that using this can reduce the running time of your algorithm on specific inputs to $O(n)$).
$$2) \quad b_j < b_k \leq a_j < a_k $$ This case is similar to the first (we get $0\leq 0$ again), and also implies that we don't need to sort for arrays of the form $\max_{i\in S}{b_i}\leq \min_{i \in S}{a_i}$.
$$3) \quad a_j \leq b_j < a_k \leq b_k$$
$$0\leq |a_j-b_k| + |a_k-b_j| - |a_j-b_j| - |a_k-b_k| = b_k-a_j + a_k-b_j - b_j+ a_j - b_k + a_k = 2a_k - 2b_j$$ Which also holds since $a_k>b_j$. Note that we could have also used $a_j < b_j \leq a_k < b_k$ and the inequality would still hold since $a_k \geq b_j$.
$$4) \quad b_j \leq a_j < b_k \leq a_k$$ $$0\leq |a_j-b_k| + |a_k-b_j| - |a_j-b_j| - |a_k-b_k| = b_k-a_j + a_k-b_j - a_j + b_j -a_k + b_k = 2b_k - 2a_j$$
Which also holds since $b_k>a_j$. We can once again also consider $b_j < a_j \leq b_k < a_k$ in which case the inequality still holds since $b_k\geq a_j$.
$$6) \quad b_j \leq a_j < a_k \leq b_k$$ $$0\leq |a_j-b_k| + |a_k-b_j| - |a_j-b_j| - |a_k-b_k| = b_k-a_j + a_k-b_j - a_j + b_j -b_k + a_k = 2a_k - 2a_j$$
The inequality holds once again since $a_k \geq a_j$.
$$6) \quad a_j \leq b_j < b_k \leq a_k$$ $$0\leq |a_j-b_k| + |a_k-b_j| - |a_j-b_j| - |a_k-b_k| = b_k-a_j + a_k-b_j + a_j - b_j -a_k + b_k = 2b_k - 2b_j$$
The inequality holds since $b_k \geq b_j$.
Thus we have verified that for all cases the inequality holds, and this proves that the solution presented in the algorithm is the optimal solution.
Another question I would like to address is why they sort. In theory you can achieve the same result by finding the minimum elements of both arrays accumulating their absolute difference and throwing them away, and then doing the same thing until you run out of items on the arrays. Finding the minimum takes as most $Cn$ time (where $C$ is a constant), considering that the array diminishes by $1$ with each iteration of this algorithm you get $\sum_{i=1}^{n}{Ci} = C\frac{n(n+1)}{2} = O(n^2)$ asymptotic running time, whereas with sorting you need only $O(n\log n)$ time.
Note also that the ifs in the for loop in the implementation available following the link are redundant.