Find the minimum possible difference between two arrays

I'll implement Shridhar's suggestion of identifying the best modification for each element individually in O(n log n) time and taking the best one.

import bisect


def abs_diff(x, y):
    return abs(x - y)


def find_nearest(sorted_a, y):
    i = bisect.bisect(sorted_a, y)
    return min(
        sorted_a[max(i - 1, 0) : min(i + 1, len(sorted_a))],
        key=lambda z: abs_diff(z, y),
    )


def improvement(x, y, z):
    return abs_diff(x, y) - abs_diff(z, y)


def min_diff(a, b):
    sorted_a = sorted(a)
    nearest = [find_nearest(sorted_a, y) for y in b]
    return sum(map(abs_diff, a, b)) - max(map(improvement, a, b, nearest))


print(min_diff([1, 3, 5], [5, 3, 1]))

This post mistakenly answers a variant of the question, which is to allow a single swap of two elements in A. I thought I'd leave it up since I worked on it.

Below are general possibilities for improvement. We can see that improvement happens when the pair we are swapping with has an opposite ordering (e.g., if a1 < b1 then a2 > b2 and vice versa). Looking more closely, we see the next quality is that the best candidate swap has the largest overlap with the first pair.

We can have an O(n log n) routine by first sorting all the given pairs by their lower element, then processing them in descending order of the lower element. As we descend, keep one order-statistic tree for the pairs where a < b and another for the pairs where b ≤ a. Order the trees by the higher element of each pair and keep two decorations: (1) the largest interval seen in the left subtree, and (2) the lowest lower element seen in the left subtree.

For each processed element, choose the larger overlap between (1) the pair in the opposite tree with an equal or lower high element and the largest interval (corresponding to the first tree decoration), and (2) the pair in the opposite tree with a higher than or equal high element and the lowest lower element (corresponding to the second tree decoration).

(Since we are processing the pairs in descending order of low, the seen lows will always be equal to or higher than the current element.)

(1)

Original:
     a1-----------b1
                     a2----b2
Total: -----------+----

Swapped:
     a1--------------------b2
                  b1-a2
Total: --------------------+-

Result: worse.

(2)

Original:
     a1-----------b1
                     b2----a2
Total: -----------+----

Swapped:
     a1--------------b2
                  b1-------a2
Total: --------------+-------

Result: worse.

(3)

Original:
     a1-----------b1
             a2------b2
Total: -----------+------

Swapped:
     a1--------------b2
             a2---b1
Total: --------------+---

Result: the same.

(4)

Original:
     a1-----------b1
             b2------a2
Total: -----------+------

Swapped:
     a1------b2
                  b1-a2
Total: ------+-

Result: BETTER.
Improvement: 2 * dist(b2, b1)

(5)

Original:
     a1--------------b1
           a2----b2
Total: --------------+----

Swapped:
     a1----------b2
           a2--------b1
Total: ----------+--------

Result: the same.

(6)

Original:
     a1--------------b1
           b2----a2
Total: --------------+----

Swapped:
     a1----b2
                 a2--b1
Total: ----+--

Result: BETTER.
Improvement: 2 * dist(b2, a2)

(7)

Original:
     a1--------------b1
 b2--------a2
Total: --------------+--------

Swapped:
 b2----a1
           a2--------b1
Total: ----+--------

Result: BETTER.
Improvement: 2 * dist(a1, a2)

(8)

Original:
     a1-----------b1
 b2-------------------a2
Total: -----------+-------------------

Swapped:
 b2--a1
                  b1--a2
Total: --+--

Result: BETTER.
Improvement: 2 * dist(a1, b1)