Minimum Absolute Sum Difference

Problem

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 <= i < 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 differenceafter replacing at most one**** element in the array nums1. Since the answer may be large, return it modulo 10^9 + 7.

|x| is defined as:

x if x >= 0, or
-x if x < 0.

Examples

Example 1

1
2
3
4
5
6


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] => [1,_**1**_ ,5], or
- Replace the second element with the third: [1,_**7**_ ,5] => [1,_**5**_ ,5].
Both will yield an absolute sum difference of |1-2| + (|1-3| or |5-3|) + |5-5| = 3.

Example 2

1
2
3
4


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

1
2
3
4


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] => [_**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

Constraints

n == nums1.length
n == nums2.length
1 <= n <= 10^5
1 <= nums1[i], nums2[i] <= 10^5

Solution

Method 1 – Binary Search + Ordered Set

Intuition

To minimize the absolute sum difference, we can replace at most one element in nums1 with another element from nums1. For each index, we want to find the closest value in nums1 to nums2[i] to minimize the difference. Using a sorted set allows us to efficiently find the closest value for each nums2[i].

Approach

Compute the initial total absolute sum difference.
Sort nums1 and use binary search to find, for each i, the closest value to nums2[i].
For each i, calculate the possible reduction in difference if we replace nums1[i] with the closest value.
Track the maximum possible reduction.
Subtract the maximum reduction from the initial sum and return the result modulo 10^9+7.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution {
public:
    int minAbsoluteSumDiff(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size(), mod = 1e9+7;
        vector<int> sorted(nums1);
        sort(sorted.begin(), sorted.end());
        int total = 0, maxRed = 0;
        for (int i = 0; i < n; ++i) {
            int diff = abs(nums1[i] - nums2[i]);
            total = (total + diff) % mod;
            auto it = lower_bound(sorted.begin(), sorted.end(), nums2[i]);
            int best = diff;
            if (it != sorted.end()) best = min(best, abs(*it - nums2[i]));
            if (it != sorted.begin()) best = min(best, abs(*(it-1) - nums2[i]));
            maxRed = max(maxRed, diff - best);
        }
        return (total - maxRed + mod) % mod;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


func minAbsoluteSumDiff(nums1 []int, nums2 []int) int {
    n, mod := len(nums1), int(1e9+7)
    sorted := append([]int{}, nums1...)
    sort.Ints(sorted)
    total, maxRed := 0, 0
    for i := 0; i < n; i++ {
        diff := abs(nums1[i]-nums2[i])
        total = (total + diff) % mod
        idx := sort.SearchInts(sorted, nums2[i])
        best := diff
        if idx < n {
            if abs(sorted[idx]-nums2[i]) < best {
                best = abs(sorted[idx]-nums2[i])
            }
        }
        if idx > 0 {
            if abs(sorted[idx-1]-nums2[i]) < best {
                best = abs(sorted[idx-1]-nums2[i])
            }
        }
        if diff-best > maxRed {
            maxRed = diff - best
        }
    }
    return (total - maxRed + mod) % mod
}
func abs(x int) int { if x < 0 { return -x }; return x }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution {
    public int minAbsoluteSumDiff(int[] nums1, int[] nums2) {
        int n = nums1.length, mod = 1000000007;
        int[] sorted = nums1.clone();
        Arrays.sort(sorted);
        int total = 0, maxRed = 0;
        for (int i = 0; i < n; ++i) {
            int diff = Math.abs(nums1[i] - nums2[i]);
            total = (total + diff) % mod;
            int idx = Arrays.binarySearch(sorted, nums2[i]);
            int best = diff;
            if (idx < 0) idx = -idx - 1;
            if (idx < n) best = Math.min(best, Math.abs(sorted[idx] - nums2[i]));
            if (idx > 0) best = Math.min(best, Math.abs(sorted[idx-1] - nums2[i]));
            maxRed = Math.max(maxRed, diff - best);
        }
        return (total - maxRed + mod) % mod;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution {
    fun minAbsoluteSumDiff(nums1: IntArray, nums2: IntArray): Int {
        val n = nums1.size
        val mod = 1_000_000_007
        val sorted = nums1.sorted()
        var total = 0
        var maxRed = 0
        for (i in 0 until n) {
            val diff = kotlin.math.abs(nums1[i] - nums2[i])
            total = (total + diff) % mod
            val idx = sorted.binarySearch(nums2[i]).let { if (it < 0) -it-1 else it }
            var best = diff
            if (idx < n) best = minOf(best, kotlin.math.abs(sorted[idx] - nums2[i]))
            if (idx > 0) best = minOf(best, kotlin.math.abs(sorted[idx-1] - nums2[i]))
            maxRed = maxOf(maxRed, diff - best)
        }
        return (total - maxRed + mod) % mod
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


def min_absolute_sum_diff(nums1: list[int], nums2: list[int]) -> int:
    from bisect import bisect_left
    mod = 10**9+7
    sorted_nums1 = sorted(nums1)
    total = 0
    max_red = 0
    for a, b in zip(nums1, nums2):
        diff = abs(a - b)
        total = (total + diff) % mod
        idx = bisect_left(sorted_nums1, b)
        best = diff
        if idx < len(sorted_nums1):
            best = min(best, abs(sorted_nums1[idx] - b))
        if idx > 0:
            best = min(best, abs(sorted_nums1[idx-1] - b))
        max_red = max(max_red, diff - best)
    return (total - max_red + mod) % mod

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


impl Solution {
    pub fn min_absolute_sum_diff(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
        use std::cmp::{min, max};
        let modv = 1_000_000_007;
        let mut sorted = nums1.clone();
        sorted.sort();
        let mut total = 0;
        let mut max_red = 0;
        for i in 0..nums1.len() {
            let diff = (nums1[i] - nums2[i]).abs();
            total = (total + diff) % modv;
            let idx = sorted.binary_search(&nums2[i]).unwrap_or_else(|x| x);
            let mut best = diff;
            if idx < sorted.len() {
                best = min(best, (sorted[idx] - nums2[i]).abs());
            }
            if idx > 0 {
                best = min(best, (sorted[idx-1] - nums2[i]).abs());
            }
            max_red = max(max_red, diff - best);
        }
        ((total - max_red + modv) % modv)
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class Solution {
    minAbsoluteSumDiff(nums1: number[], nums2: number[]): number {
        const mod = 1_000_000_007;
        const sorted = [...nums1].sort((a, b) => a - b);
        let total = 0, maxRed = 0;
        for (let i = 0; i < nums1.length; ++i) {
            const diff = Math.abs(nums1[i] - nums2[i]);
            total = (total + diff) % mod;
            let l = 0, r = sorted.length-1, best = diff;
            while (l <= r) {
                const m = Math.floor((l+r)/2);
                if (sorted[m] < nums2[i]) l = m+1;
                else r = m-1;
            }
            if (l < sorted.length) best = Math.min(best, Math.abs(sorted[l] - nums2[i]));
            if (l > 0) best = Math.min(best, Math.abs(sorted[l-1] - nums2[i]));
            maxRed = Math.max(maxRed, diff - best);
        }
        return (total - maxRed + mod) % mod;
    }
}

Complexity

⏰ Time complexity: O(n log n)
- Sorting nums1 and binary search for each index.
🧺 Space complexity: O(n)
- For sorted copy of nums1.

Problem#

Examples#

Example 1#

Example 2#

Example 3#

Constraints#

Solution#

Method 1 – Binary Search + Ordered Set#

Intuition#

Approach#

Code#

Complexity#