Suppose you are given two arrays of the same length $n$, say $a$ and $b$ containing unique positive integers. The L1 distance between $a$ and $b$ is defined as: $$d_1(a, b) = \sum_{i = 1}^n \lvert a_i - b_i \rvert$$ (assuming 1-indexing for convenience)

You are allowed to permute $a$ and $b$ and the goal is to minimize $d_1(a, b)$, or equivalently find a permutation which minimizes the L1 distance. As a corollary, you also need to prove that there is a unique mapping of elements of $a$ and $b$ for which this minimum is achieved, or equivalently, for a given permutation of $a$, only a unique permutation of $b$ can minimize the L1 distance.

My approach

The first trivial observation I made is that one can keep one of the arrays fixed and permute the other. So without loss of generality, let us keep $a$ and use the permutation where $a$ is sorted in increasing order and permute $b$. Taking several examples leads to the conclusion that $d_1(a, b)$ is minimized when $b$ is also sorted in increasing order. Take a few examples to demonstrate this fact:

  1. $a = \{1, 5, 7\}\quad b = \{6, 3, 2\}$. For various permutations of $b$, the L1 distances are:
    • $b = \{2, 3, 6\}$, $d_1(a, b) = 4$
    • $b = \{2, 6, 3\}$, $d_1(a, b) = 6$
    • $b = \{3, 2, 6\}$, $d_1(a, b) = 6$
    • $b = \{3, 6, 2\}$, $d_1(a, b) = 8$
    • $b = \{6, 2, 3\}$, $d_1(a, b) = 13$
    • $b = \{6, 3, 2\}$, $d_1(a, b) = 12$
  2. $a = \{1, 4, 5, 9\}\quad b = \{1, 3, 2, 6\}$. By programmatically listing down and calculating the L1 distance of all the permutations of $b$, one can prove that the minimum is achieved for the permutation where $b$ is sorted.

I tried to prove it by contradiction by assuming that $b$ is a sorted permutation, i.e. $b_1 \leq b_2 \leq \ldots b_n$ and $c$ is any other permutation. I am trying to prove that: $$ \left(d_1(a, b) > d_1(a, c) \right) \Rightarrow \text{Contradiction}$$ However, I haven't been able to proceed. How do I prove the claim?


3 Answers 3


Prove the lemma for arrays in two dimensions. That is, show that if $a_1 > a_2$ and $b_1 > b_2$, then $\vert a_1-b_1\vert + \vert a_2-b_2\vert < \vert a_2-b_1\vert + \vert a_1-b_2\vert $. Possibly there are smart ways to do that. But at worst, you can show this is true by completely enumerating all six possible cases:

  • $a_1 > a_2 > b_1 > b_2$
  • $a_1 > b_1 > a_2 > b_2$
  • $a_1 > b_1 > b_2> a_2$
  • $b_1 > a_1 > a_2 > b_2$
  • $b_1 > a_1 > b_2 > a_2$
  • $b_1 > b_2 > a_1 > a_2$

Once this is done, your approach is now straight forward. Consider a fixed vector $a$ that is already sorted. Now, if $b$ is unsorted, then by the above lemma, there exists a swap that necessarily reduces the $\ell_1$ norm.


Yes, two sorted sequences will always give you the minimum $l_1$ distance. Suppose that is not the case. Without loss of generality, assume that all $a_i$s are sorted but $b_i$s aren't. So there must be two indices, $i$ and $j$ ($i < j$), such that $b_i > b_j$. We will now show that swapping these two values decreases the overall cost, which contradicts the assumption that an unsorted sequence of $b_i$ gives the minimum cost.

Thus, we need to show that $|a_i - b_i| + |a_j - b_j| \ge |a_i - b_j| + |a_j - b_i|$.

Let $a_i + x = a_j$ and $b_j + y = b_i$ for some $x\ge 0$ and $y > 0$.

Now suppose $a_i - b_j \ge 0$. Then we have \begin{aligned} |a_i - b_i| + |a_j - b_j| &= |a_i - b_j - y| + |a_i - b_j + x|\\ &= |a_i - b_j - y| + |a_i - b_j| + x\\ &\ge |a_i - b_j + x - y| + |a_i - b_j|\\ &= |a_i - b_j| + |a_j - b_i| \end{aligned}

Similarly, when $a_i - b_j < 0$, we have \begin{aligned} |a_i - b_i| + |a_j - b_j| &= |a_i - b_j - y| + |a_i - b_j + x|\\ &= |b_j - a_i + y| + |b_j - a_i - x|\\ &\ge |b_j - a_i| + |b_j - a_i - x + y|\\ &= |a_i - b_j| + |a_i - b_j + x - y|\\ &= |a_i - b_j| + |a_j - b_i| \end{aligned}

PS: The idea is based on this post, which asks a similar problem but for the $l_2$ norm.


You can formulate this problem as a weighted version of maximum bipartite matching problem.

For each element $a_i$, create a vertex $u_i$, and for element $b_j$, create a vertex $v_j$. Let us define $U = \{a_i\}$ and $V = \{b_j\}$. Now for every pair of elements $(a_i, b_j)$ put an edge $(u_i, v_j)$ with weight $w_{i,j} = -|a_i - b_j|$. Now solve the maximum weight bipartite matching. This can be solved in polynomial time [ref: Hungarian Algorithm].

  • $\begingroup$ This gives an algorithm to solve the problem, however, I already have an algorithm to solve it, i.e. just sort the two arrays and take the sum of absolute difference between the elements. This can be solved in $\mathcal{O}(n \log n)$ as opposed to $\mathcal{O}(n^3)$ which the Hungarian Algorithm takes. The Wikipedia page you mentioned doesn't prove the version I have asked. Could you help me with proving optimality? $\endgroup$
    – kaddy
    Commented Jun 14 at 9:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.