Minimum Absolute Sum Difference

Medium
1383.

Minimum Absolute Sum Difference

Minimum Absolute Sum Difference is a medium coding problem on arrays, sorting and binary search, asked in Amazon and Google interviews.

nums1 and nums2 both have length n. Their absolute sum difference is the sum of |nums1[i] - nums2[i]| over all i.

You may perform at most one replacement: overwrite one element of nums1 with a copy of any element of nums1 (possibly the same one).

Return the smallest absolute sum difference you can reach. The sum can be large, so return it modulo 10^9 + 7 — apply the modulus only to the final minimum.

Example 1

Input
nums1 = [1,7,5], nums2 = [2,3,5]
Output
3
Explanation
Replace the 7 with a 1 (or a 5): |1-2| + |1-3| + |5-5| = 3.

Example 2

Input
nums1 = [2,4,6,8,10], nums2 = [2,4,6,8,10]
Output
0

Example 3

Input
nums1 = [1,10,4,4,2,7], nums2 = [9,3,5,1,7,4]
Output
20
Explanation
Replacing the first element with 10 turns |1-9| = 8 into |10-9| = 1.

Constraints

  • n == nums1.length == nums2.length
  • 1 <= n <= 10^5
  • 1 <= nums1[i], nums2[i] <= 10^5
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var minAbsoluteSumDiff = function(nums1, nums2) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Absolute Sum Difference — Problem & Solution

Minimum Absolute Sum Difference solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Minimum Absolute Sum Difference is a medium coding problem on arrays, sorting and binary search, asked in Amazon and Google interviews.

Problem statement

nums1 and nums2 both have length n. Their absolute sum difference is the sum of |nums1[i] - nums2[i]| over all i.

You may perform at most one replacement: overwrite one element of nums1 with a copy of any element of nums1 (possibly the same one).

Return the smallest absolute sum difference you can reach. The sum can be large, so return it modulo 10^9 + 7 — apply the modulus only to the final minimum.

Example 1

Input: nums1 = [1,7,5], nums2 = [2,3,5]
Output: 3
Explanation: Replace the 7 with a 1 (or a 5): |1-2| + |1-3| + |5-5| = 3.

Example 2

Input: nums1 = [2,4,6,8,10], nums2 = [2,4,6,8,10]
Output: 0

Example 3

Input: nums1 = [1,10,4,4,2,7], nums2 = [9,3,5,1,7,4]
Output: 20
Explanation: Replacing the first element with 10 turns |1-9| = 8 into |10-9| = 1.

Constraints

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

Hints for Minimum Absolute Sum Difference

  1. Hint 1

    Only one position changes, so the best move is the one that reduces the total the most.

  2. Hint 2

    If you overwrite position i, the best value to write is the element of nums1 closest to nums2[i].

  3. Hint 3

    Sort a copy of nums1 and binary-search, for every i, the neighbours of nums2[i]; track the largest saving |nums1[i] - nums2[i]| - closest.

How to solve Minimum Absolute Sum Difference

The total minus the largest possible saving is the answer. The saving at position i is its current difference minus the distance from nums2[i] to the nearest value in nums1, which a sorted copy plus binary search finds.

Approach

  1. Sort a copy s of nums1.
  2. For each i, add d = |nums1[i] - nums2[i]| to a 64-bit total.
  3. Binary-search the lower bound of nums2[i] in s; the closest value is s[j] or s[j - 1].
  4. Record best = max(best, d - closest distance).
  5. Return (total - best) mod (10^9 + 7).

Why it works

Changing position i only affects the i-th term, so the new total is total - d_i + c_i where c_i is the new term; picking the nearest available value minimises c_i. Among the n choices of position the largest d_i - c_i gives the smallest result, and doing nothing corresponds to a saving of 0.

Complexity

  • Time — O(n log n)
  • Space — O(n)

Pitfalls

  • Take the modulus only at the end — reducing the total first and then subtracting the saving can go negative or pick the wrong minimum.
  • The total can reach 10^10, so accumulate in 64-bit.
  • Search the sorted copy of nums1, not nums2: the replacement must come from nums1.

Reference solution

Python

from typing import List
import bisect

def minAbsoluteSumDiff(nums1: List[int], nums2: List[int]) -> int:
    s = sorted(nums1)
    n = len(s)
    total = 0
    best = 0
    for a, b in zip(nums1, nums2):
        d = abs(a - b)
        total += d
        j = bisect.bisect_left(s, b)
        c = d
        if j < n:
            c = min(c, s[j] - b)
        if j > 0:
            c = min(c, b - s[j - 1])
        best = max(best, d - c)
    return (total - best) % 1000000007

Java

public static int minAbsoluteSumDiff(int[] nums1, int[] nums2) {
    int n = nums1.length;
    int[] s = nums1.clone();
    Arrays.sort(s);
    long total = 0;
    int best = 0;
    for (int i = 0; i < n; i++) {
        int b = nums2[i];
        int d = Math.abs(nums1[i] - b);
        total += d;
        int lo = 0, hi = n;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (s[mid] < b) lo = mid + 1; else hi = mid;
        }
        int c = d;
        if (lo < n) c = Math.min(c, s[lo] - b);
        if (lo > 0) c = Math.min(c, b - s[lo - 1]);
        best = Math.max(best, d - c);
    }
    return (int) ((total - best) % 1000000007L);
}

C++

int minAbsoluteSumDiff(vector<int>& nums1, vector<int>& nums2) {
    int n = nums1.size();
    vector<int> s(nums1);
    sort(s.begin(), s.end());
    long long total = 0;
    int best = 0;
    for (int i = 0; i < n; i++) {
        int b = nums2[i];
        int d = abs(nums1[i] - b);
        total += d;
        int j = lower_bound(s.begin(), s.end(), b) - s.begin();
        int c = d;
        if (j < n) c = min(c, s[j] - b);
        if (j > 0) c = min(c, b - s[j - 1]);
        best = max(best, d - c);
    }
    return (int)((total - best) % 1000000007LL);
}

JavaScript

var minAbsoluteSumDiff = function(nums1, nums2) {
    var n = nums1.length;
    var s = nums1.slice().sort(function(a, b) { return a - b; });
    var total = 0, best = 0;
    for (var i = 0; i < n; i++) {
        var b = nums2[i];
        var d = Math.abs(nums1[i] - b);
        total += d;
        var lo = 0, hi = n;
        while (lo < hi) {
            var mid = (lo + hi) >> 1;
            if (s[mid] < b) lo = mid + 1; else hi = mid;
        }
        var c = d;
        if (lo < n && s[lo] - b < c) c = s[lo] - b;
        if (lo > 0 && b - s[lo - 1] < c) c = b - s[lo - 1];
        if (d - c > best) best = d - c;
    }
    return (total - best) % 1000000007;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms