You are given two integer arrays a and b of the same length.

Let's define the difference between a and b as the sum of absolute differences of corresponding elements:

  difference = |a[0] - b[0]| |a[1] - b[1]| …

You can replace one element of a with any other element of a.
Your task is to return the minimum possible difference between a and b that can be achieved by performing at most one such replacement on a.
You can also choose to leave the array intact.

Example

For a = [1, 3, 5] and b = [5, 3, 1] , the output should be solution(a, b) = 4.

• If we leave the array a intact, the difference: |1 - 5| |3 - 3| |5 - 1| = 8.
• If we replace a[0] with a[1], we get
  [3, 3, 5] and the difference is |3 - 5| |3 - 3| |5 - 1| = 6;
• If we replace a[0] with a[2], we get
  [5, 3, 5] and the difference is |5 - 5| |3 - 3| |5 - 1| = 4;
• If we replace a[1] with a[0], we get
  [1, 1, 5] and the difference is |1 - 5| |1 - 3| |5 - 1| = 10;
• If we replace a[1] with a[2], we get
  [1, 5, 5] and the difference is |1 - 5| |5 - 3| |5 - 1| = 10;
• If we replace a[2] with a[0], we get
  [1, 3, 1] and the difference is |1 - 5| |5 - 3| |1 - 1| = 4;
• If we replace a[2] with a[1] we get
  [1, 3, 3] and the difference is |1 - 5| |3 - 3| |3 - 1| = 6;

So the final answer is 4.

The solution must be at most, O(n log n) complexity.

CodePudding user response：

The general idea is this: Sweep both arrays for absolute differences and keep track of individual abs differences and the corresponding elements in both array in a max heap. This allows you to start checking the most promising ones. Sort the elements of A. Take elements out of the max heap one by one and binary search in the sorted A copy for complements that reduce the abs difference. once you found a pair that reduces the difference greater than or equal to the next item in the max heap, you have found your solution since you can be sure there is no better pair. This is linearithmic, but may not be the most optimal.

import heapq, bisect

def best_diff(A, B): 
    hp = [] # max heap store
    res = 0 # sum of diffs

    for a, b in zip(A, B): 
        hp.append((-abs(a-b), a, b)) 
        res  = abs(a-b) 
    heapq.heapify(hp) # heapify once to keep it linear
    A_sorted = list(sorted(A)) 
    best_change = float("-inf") # we want to maximize this

    while hp: 
        diff, a, b = heapq.heappop(hp) 
        diff = abs(diff) 

        # we are looking for an a as close to b as possible
        # to minimize diff and maximize change
        idx = bisect.bisect_left(A_sorted, b) 
        new_diff = abs(A_sorted[idx]-b) 
        if new_diff < diff: 
            best_change = max(best_change, diff - new_diff) 

            # if the change we have achieved is greater than
            # the next diff in the max heap, we bail out early
            # because we can't do better
            if best_change >= -hp[0][0]: 
                return res - best_change 
                     
    return res - best_change

# simple test
# In [11]: best_diff([1,3,5], [5,3,1])                                  
# Out[11]: 4

Time complexity analysis: We do a linear loop on A and B. This is O(n) where n is the length of A or B. Heapify is also O(n). Sorting A and (in the worst case) popping all elements of A out of the heap is linearithmic, O(n log n). So this becomes O(n log n).

Space complexity: O(n) for the heap. We could sort in-place and avoid the extra array.

Word of caution: I haven't tested the code nearly enough. Only ran it on your input example. The idea and concept are correct as far as I understand but there may be edge cases that I haven't thought of. For example: What if all of As elements are less than the absolute diff? Then bisect returns and idx equal to the length of A which we are using without checking and it will through an out of bound error. Another edge case is when the element at idx-1 has a smaller abs diff to the target we are seeking than the element at idx.

I leave that to you to shape out.

CodePudding user response：

The goal is to find the most similar number in a for all elements in b because the minimum absolute difference can be reduced by replacing one of those pairs.

Finding a similar number for one element will take O(log n) using the bisect algorithm. So total time complexity will be O(n log n).

Here is the solution.

import bisect


class Solution(object):
    def minAbsoluteSumDiff(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: int
        """
        MOD = 10**9 7

        sorted_nums1 = sorted(nums1)
        result = max_change = 0
        for i in xrange(len(nums2)):
            diff = abs(nums1[i]-nums2[i])
            result = (result diff)%MOD
            if diff < max_change:
                continue
            j = bisect.bisect_left(sorted_nums1, nums2[i])
            if j != len(sorted_nums1):
                max_change = max(max_change, diff-abs(sorted_nums1[j]-nums2[i]))
            if j != 0:
                max_change = max(max_change, diff-abs(sorted_nums1[j-1]-nums2[i]))
        return (result-max_change)%MOD