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.
- Difficulty: Medium
- Topics: Arrays, Sorting, Binary Search, Ordered Set
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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.length1 <= n <= 10^51 <= nums1[i], nums2[i] <= 10^5
Hints for Minimum Absolute Sum Difference
Hint 1
Only one position changes, so the best move is the one that reduces the total the most.
Hint 2
If you overwrite position
i, the best value to write is the element ofnums1closest tonums2[i].Hint 3
Sort a copy of
nums1and binary-search, for everyi, the neighbours ofnums2[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
- Sort a copy
sofnums1. - For each
i, addd = |nums1[i] - nums2[i]|to a 64-bit total. - Binary-search the lower bound of
nums2[i]ins; the closest value iss[j]ors[j - 1]. - Record
best = max(best, d - closest distance). - 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, notnums2: the replacement must come fromnums1.
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) % 1000000007Java
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