Problem Description

You are given two integer arrays nums1 and nums2, both of length n. The absolute sum difference of these arrays is defined as the sum of |nums1[i] - nums2[i]| for all valid indices i (from 0 to n-1).

You are allowed to replace at most one element in nums1 with any other element from nums1 (i.e., you can swap one value in nums1 with any other value from nums1, possibly itself).

Your goal is to minimize the absolute sum difference after performing at most one such replacement. Return the minimum possible absolute sum difference modulo 10^9 + 7.

• Each input array can contain up to 105 elements.
• All elements are positive integers less than 105.
• You may not use elements from nums2 to replace elements in nums1.

Thought Process

The problem asks us to minimize the total difference between two arrays by changing at most one element in the first array. A brute-force approach would be to try every possible replacement for every position, but with large arrays, this would be too slow.

Instead, we realize that for each index i, we want to see if we can replace nums1[i] with another value from nums1 to make nums1[i] as close as possible to nums2[i]. If we can make nums1[i] equal to nums2[i], the difference at that position becomes zero, which is optimal.

To do this efficiently, we need a way to quickly find, for each nums2[i], the value in nums1 that is closest to it. This suggests using binary search on a sorted copy of nums1.

Solution Approach

• Step 1: Compute the initial absolute sum difference by summing |nums1[i] - nums2[i]| for all indices.
• Step 2: Sort a copy of nums1 to allow fast binary search for the closest value to any nums2[i].
• Step 3: For each index i:
  • Use binary search to find the value in the sorted nums1 that is closest to nums2[i].
  • Calculate the potential new difference if nums1[i] were replaced by this closest value.
  • Track the maximum possible reduction in the total sum difference across all positions.
• Step 4: Subtract the maximum possible reduction from the initial sum to get the answer.
• Step 5: Return the answer modulo 10^9 + 7.

We use a sorted array and binary search because searching for the closest value in an unsorted array would be too slow (O(n) per query), but with sorting, we can do it in O(log n) per query.

Example Walkthrough

Input: nums1 = [1,7,5], nums2 = [2,3,5]

• Initial absolute differences: |1-2| = 1, |7-3| = 4, |5-5| = 0. Total = 1 + 4 + 0 = 5.
• Sorted nums1: [1,5,7]
• For index 0 (nums2[0]=2): Closest in nums1 is 1 (diff=1) or 5 (diff=3). No improvement.
  For index 1 (nums2[1]=3): Closest in nums1 is 1 (diff=2) or 5 (diff=2). Current diff is 4, could reduce to 2.
  For index 2 (nums2[2]=5): Closest is 5 (diff=0). Already optimal.
• The best possible reduction is at index 1: reduce difference from 4 to 2 (improvement of 2).
• Final answer: 5 - 2 = 3

Time and Space Complexity

• Brute-force approach: For each position, try replacing with every other element in nums1 (O(n^2)), which is not feasible for large n.
• Optimized approach:
  • Sorting nums1: O(n log n)
  • For each of n positions, binary search for closest value: O(n log n)
  • Total: O(n log n) time
  • Space: O(n) for the sorted copy

Summary

The key insight is to recognize that replacing a value in nums1 with the value closest to nums2[i] can minimize the absolute difference at that index. By pre-sorting nums1, we can efficiently find the closest value using binary search, allowing us to compute the optimal replacement in O(n log n) time. This approach balances correctness and performance, making it suitable for large input sizes.

Code Implementation

import bisect

class Solution:
    def minAbsoluteSumDiff(self, nums1, nums2):
        MOD = 10 ** 9 + 7
        n = len(nums1)
        sorted_nums1 = sorted(nums1)
        total = 0
        max_gain = 0

        for i in range(n):
            a, b = nums1[i], nums2[i]
            diff = abs(a - b)
            total += diff

            idx = bisect.bisect_left(sorted_nums1, b)
            # Try the closest value on the left
            if idx > 0:
                gain = diff - abs(sorted_nums1[idx-1] - b)
                if gain > max_gain:
                    max_gain = gain
            # Try the closest value on the right
            if idx < n:
                gain = diff - abs(sorted_nums1[idx] - b)
                if gain > max_gain:
                    max_gain = gain

        return (total - max_gain) % MOD
      

#include <vector>
#include <algorithm>
#include <cstdlib>

using namespace std;

class Solution {
public:
    int minAbsoluteSumDiff(vector<int>& nums1, vector<int>& nums2) {
        const int MOD = 1e9 + 7;
        int n = nums1.size();
        vector<int> sorted_nums1(nums1);
        sort(sorted_nums1.begin(), sorted_nums1.end());
        long total = 0, max_gain = 0;

        for (int i = 0; i < n; ++i) {
            int a = nums1[i], b = nums2[i];
            int diff = abs(a - b);
            total += diff;

            auto it = lower_bound(sorted_nums1.begin(), sorted_nums1.end(), b);
            if (it != sorted_nums1.begin()) {
                max_gain = max(max_gain, (long)diff - abs(*(it - 1) - b));
            }
            if (it != sorted_nums1.end()) {
                max_gain = max(max_gain, (long)diff - abs(*it - b));
            }
        }
        return (total - max_gain + MOD) % MOD;
    }
};
      

import java.util.*;

class Solution {
    public int minAbsoluteSumDiff(int[] nums1, int[] nums2) {
        int MOD = 1_000_000_007;
        int n = nums1.length;
        int[] sorted = nums1.clone();
        Arrays.sort(sorted);
        long total = 0, maxGain = 0;

        for (int i = 0; i < n; ++i) {
            int a = nums1[i], b = nums2[i];
            int diff = Math.abs(a - b);
            total += diff;

            int idx = Arrays.binarySearch(sorted, b);
            if (idx < 0) idx = -idx - 1;

            if (idx > 0) {
                maxGain = Math.max(maxGain, diff - Math.abs(sorted[idx - 1] - b));
            }
            if (idx < n) {
                maxGain = Math.max(maxGain, diff - Math.abs(sorted[idx] - b));
            }
        }
        return (int)((total - maxGain + MOD) % MOD);
    }
}
      

var minAbsoluteSumDiff = function(nums1, nums2) {
    const MOD = 1e9 + 7;
    const n = nums1.length;
    let sorted = nums1.slice().sort((a, b) => a - b);
    let total = 0;
    let maxGain = 0;

    for (let i = 0; i < n; ++i) {
        let a = nums1[i], b = nums2[i];
        let diff = Math.abs(a - b);
        total += diff;

        // Binary search for closest value in sorted
        let left = 0, right = n - 1;
        while (left < right) {
            let mid = Math.floor((left + right) / 2);
            if (sorted[mid] < b) left = mid + 1;
            else right = mid;
        }
        // Check left and left-1
        if (left > 0) {
            maxGain = Math.max(maxGain, diff - Math.abs(sorted[left - 1] - b));
        }
        if (left < n) {
            maxGain = Math.max(maxGain, diff - Math.abs(sorted[left] - b));
        }
    }
    return (total - maxGain + MOD) % MOD;
};