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

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