You are given two positive integer arrays nums1 and nums2, both of length n.

The absolute sum difference of arrays nums1 and nums2 is defined as the sum of |nums1[i] - nums2[i]| for each 0 &lt;= i &lt; n (0-indexed).

You can replace at most one element of nums1 with any other element in nums1 to minimize the absolute sum difference.

Return the minimum absolute sum difference after replacing at most one element in the array nums1. Since the answer may be large, return it modulo 109 + 7.

|x| is defined as:


	x if x &gt;= 0, or
	-x if x &lt; 0.


&nbsp;
Example 1:

Input: nums1 = [1,7,5], nums2 = [2,3,5]
Output: 3
Explanation: There are two possible optimal solutions:
- Replace the second element with the first: [1,7,5] =&gt; [1,1,5], or
- Replace the second element with the third: [1,7,5] =&gt; [1,5,5].
Both will yield an absolute sum difference of |1-2| + (|1-3| or |5-3|) + |5-5| = 3.


Example 2:

Input: nums1 = [2,4,6,8,10], nums2 = [2,4,6,8,10]
Output: 0
Explanation: nums1 is equal to nums2 so no replacement is needed. This will result in an 
absolute sum difference of 0.


Example 3:

Input: nums1 = [1,10,4,4,2,7], nums2 = [9,3,5,1,7,4]
Output: 20
Explanation: Replace the first element with the second: [1,10,4,4,2,7] =&gt; [10,10,4,4,2,7].
This yields an absolute sum difference of |10-9| + |10-3| + |4-5| + |4-1| + |2-7| + |7-4| = 20


&nbsp;
Constraints:


	n == nums1.length
	n == nums2.length
	1 &lt;= n &lt;= 105
	1 &lt;= nums1[i], nums2[i] &lt;= 105


class Solution:
    def minAbsoluteSumDiff(self, nums1: List[int], nums2: List[int]) -> int:
        n = len(nums1)
        diff = []
        sum = 0
        for i in range(n):
            temp = abs(nums1[i]-nums2[i])
            diff.append(temp)
            sum += temp
        nums1.sort()
        best_diff = []
        for i in range(n):
            idx = bisect.bisect_left(nums1, nums2[i])
            if idx != 0 and idx != n:
                best_diff.append(
                    min(abs(nums2[i]-nums1[idx]), abs(nums2[i]-nums1[idx-1])))
            elif idx == 0:
                best_diff.append(abs(nums2[i]-nums1[idx]))
            else:
                best_diff.append(abs(nums2[i]-nums1[idx-1]))
        saved = 0
        for i in range(n):
            saved = max(saved, diff[i]-best_diff[i])
        return (sum-saved) % ((10**9)+(7))
class Solution {
    public int minAbsoluteSumDiff(int[] nums1, int[] nums2) {
        int mod = (int)1e9+7;

        // Sorted copy of nums1 to use for binary search
        int[] snums1 = nums1.clone();
        Arrays.sort(snums1);
        
        int maxDiff = 0;    // maximum difference between original and new absolute diff
        int pos = 0;        // where the maximum difference occurs
        int newn1 = 0;      // nums1 value to copy to nums1[pos]

        // For each array position i from 0 to n-1, find up to two elements
        // in nums1 that are closest to nums2[i] (one on each side of nums2[i]).
        // Calculate a new absolute difference for each of these elements.
        for (int i=0; i<nums2.length; i++) {
            int n2 = nums2[i];
            int origDiff = Math.abs(nums1[i] - n2);
            
            // Find the largest element in nums1 that is less than or equal to
            // the current element in nums2, if such an element exists.
            int floor = arrayFloor(snums1, n2);
            if (floor > Integer.MIN_VALUE) {
                // If a valid element exists, calculate a new absolute difference
                // at the current position, and calculate how much smaller this is
                // than the current absolute difference. If the result is better
                // than what we have seen so far, update the maximum difference and
                // save the data for the current position.
                int newDiff = Math.abs(floor - n2);
                int diff = origDiff - newDiff;
                if (diff > maxDiff) {
                    pos = i;
                    newn1 = floor;
                    maxDiff = diff;
                }
            }
            
            // Find the smallest element in nums1 that is greater than or equal to
            // the current element in nums2, if such an element exists.
            int ceiling = arrayCeiling(snums1, n2);
            if (ceiling < Integer.MAX_VALUE) {
                // Same as above
                int newDiff = Math.abs(ceiling - n2);
                int diff = origDiff - newDiff;
                if (diff > maxDiff) {
                    pos = i;
                    newn1 = ceiling;
                    maxDiff = diff;
                }
            }
        }

        // If we found a replacement value, overwrite the original value.
        if (newn1 > 0) {
            nums1[pos] = newn1;
        }
        
        // Calculate the absolute sum difference with the replaced value.
        int sum = 0;
        for (int i=0; i<nums1.length; i++) {
            sum = (sum + Math.abs(nums1[i] - nums2[i])) % mod;
        }
        
        return sum;
    }


    //
    // Array versions of TreeSet.floor and TreeSet.ceiling
    //
    
    // Greatest element less than or equal to val
    private int arrayFloor(int[] arr, int val) {
        int lo = 0;
        int hi = arr.length-1;
        int max = Integer.MIN_VALUE;
        
        while (lo <= hi) {
            int mid = lo+(hi-lo)/2;
            if (arr[mid] <= val) {
                max = arr[mid];
                lo = mid+1;
            } else {
                hi = mid-1;
            }
        }
        
        return max;
    }
    
    // Smallest element greater than or equal to val
    private int arrayCeiling(int[] arr, int val) {
        int lo = 0;
        int hi = arr.length-1;
        int min = Integer.MAX_VALUE;
        
        while (lo <= hi) {
            int mid = lo+(hi-lo)/2;
            if (arr[mid] >= val) {
                min = arr[mid];
                hi = mid-1;
            } else {
                lo = mid+1;
            }
        }
        
        return min;
    }
}
class Solution {
public:
    int minAbsoluteSumDiff(vector<int>& nums1, vector<int>& nums2) {
      long sum=0, minSum;
      vector<int> nums=nums1;
      int n=nums.size();
	  // Calculate the current sum of differences.
      for(int i=0;i<n;i++) sum+=abs(nums1[i]-nums2[i]);
      
      sort(nums.begin(), nums.end());
      minSum=sum;
      
      for(int i=0;i<n;i++) {
        int dist=abs(nums1[i]-nums2[i]);
        int l=0, h=n-1;
        
		// Find the number closest to nums2[i]. 
		// The closer the element, the smaller the difference.
        while(l<h) {
          int m=l+(h-l)/2;
          if(nums[m]>nums2[i]) {
            h=m;
          } else {
            l=m+1;
          }
          dist=min(dist, abs(nums2[i]-nums[m]));
        }
        dist=min(dist, abs(nums2[i]-nums[l]));
        minSum = min(minSum, sum - abs(nums1[i]-nums2[i]) + dist);
      }
      
      return minSum % 1000000007;
    }
};
var minAbsoluteSumDiff = function(nums1, nums2) {
    const MOD = 1e9 + 7;
    const n = nums1.length;

    const origDiffs = [];
    let diffSum = 0;

    for (let i = 0; i < n; i++) {
        const num1 = nums1[i];
        const num2 = nums2[i];

        const currDiff = Math.abs(num1 - num2);

        origDiffs[i] = currDiff;
        diffSum += currDiff;
    }

    nums1.sort((a, b) => a - b);

    let minDiffSum = diffSum;

    for (let i = 0; i < n; i++) {
        const origDiff = origDiffs[i];

        const num2 = nums2[i];

        let left = 0;
        let right = n - 1;

        let bestDiff = origDiff;

        while (left <= right) {
            const mid = (left + right) >> 1;
            const num1 = nums1[mid];

            const candDiff = num1 - num2;

            if (Math.abs(candDiff) < bestDiff) {
                bestDiff = Math.abs(candDiff);
                if (bestDiff === 0) break;
            }

            if (candDiff < 0) left = mid + 1;
            else right = mid - 1;
        }

        const replacedDiffSum = (diffSum - origDiff) + bestDiff;

        minDiffSum = Math.min(minDiffSum, replacedDiffSum);
    }

    return minDiffSum % MOD;
};
Minimum Absolute Sum Difference