Find the minimum possible difference between two arrays

Question

I am struggling to figure out an efficient algorithm to perform the following task:

Given two arrays A and B with equal length, the difference between the two arrays is defined as:

diff = |a[0]-b[0]| + |a[1]-b[1]| +...+|a[a.length-1]-b[b.length-1]|

I am required to find the minimum possible difference between A and B, and I am allowed to replace at most one element from A with any other element in A. Note that you are not required to perform a replacement.

For example:

A = [1,3,5]
B = [5,3,1]

If we replace A[2] with A[0], then the difference between the two arrays is:

|1-5| + |3-3| + |1-1| = 4

This is the minimal possible difference between the two arrays. No other replacement of an element in A with another element in A would result in a smaller difference between A and B.

How would I go about solving this problem? I know how to solved the problem in O(n^2) (brute force), but struggling to figure out a more efficient way.

Thanks!

Answer 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)

Answer 2

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]))