Minimum Absolute Sum Difference solution and explanation
8 more videos on this problem
LeetCode 1818. Minimum Absolute Sum Difference | Medium | 🏆 Weekly Contest 235 | Algorithm ExplainedCherry Coding [IIT-G] · 13:49 · 9K views
1818. Minimum Absolute Sum Difference (Leetcode Medium)Programming Live with Larry · 8:22 · 2K views
LeetCode 1818 Minimum Absolute Sum Difference | Python Solution #python #1818AI Learning Corner · 12:49 · 728 views
Leetcode 1818. Minimum Absolute Sum DifferenceElite Code · 30:09 · 678 views
Leetcode 1818. Minimum Absolute Sum Difference (Ordered Set)LetsCode · 21:28 · 245 views
大壮刷题 - 1818. Minimum Absolute Sum Difference, Medium, Binary Search大壮刷题 · 8:31 · 145 views
LeetCode Medium 1818 Minimum Absolute Sum Differencerobzingcod · 14:38 · 87 views
Leetcode - 1818. Minimum Absolute Sum Difference | Live SolutionKrispy Coding · 41:35 · 63 views
LeetCode 1818: Minimum Absolute Sum DifferenceAlitaCode · 29:35 · 12 views
The 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 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:
xifx >= 0, or-xifx < 0.
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] => [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:
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] => [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.lengthn == nums2.length1 <= n <= 1051 <= nums1[i], nums2[i] <= 105
Approach overview
Problem Overview: You are given two arrays nums1 and nums2 of equal length. The cost is the sum of |nums1[i] - nums2[i]| for every index. You may replace at most one element in nums1 with any other value already present in nums1. The goal is to minimize the total absolute difference.
Approach 1: Brute Force Replacement (O(n^2) time, O(1) space)
First compute the baseline sum of |nums1[i] - nums2[i]|. Then try improving it by replacing nums1[i] with every possible value from nums1. For each index i, iterate through the entire array and calculate the new difference if that value were used instead. Track the maximum reduction achievable from a single replacement. This approach directly simulates the operation but requires nested iteration over the array, resulting in O(n^2) time. It works for small inputs and clearly demonstrates the optimization opportunity.
Approach 2: Sorted Array + Binary Search (O(n log n) time, O(n) space)
The key observation: when replacing nums1[i], the best candidate is the value in nums1 closest to nums2[i]. Instead of scanning the entire array, sort a copy of nums1. For each index i, use binary search to locate the closest value to nums2[i] in the sorted array. Compare both the insertion position and its neighbor to find the minimum possible difference. Compute how much this replacement would reduce the current absolute difference, and track the maximum improvement. Finally subtract that improvement from the baseline sum. Sorting enables fast lookups, reducing the total complexity to O(n log n). This technique combines Array traversal with Binary Search on a sorted structure.
Recommended for interviews: The binary search optimization is the expected solution. Interviewers want to see you recognize that only the closest value to nums2[i] matters, which allows replacing a quadratic scan with a logarithmic lookup. Starting with the brute force approach shows you understand the operation, but transitioning to a sorted array and binary search demonstrates strong algorithmic thinking.
Approach 1: Brute Force Approach
The naive brute force approach involves iterating through each element of the nums1 array and trying to replace it with every other element from the array. For each replacement, compute the absolute sum difference and keep track of the minimum difference encountered. While simple, this approach is inefficient due to its O(n^2) time complexity, which can be impractical for large input sizes.
def minAbsoluteSumDiff(nums1, nums2):
MOD = 10**9 + 7
n = len(nums1)
total_diff = sum(abs(nums1[i] - nums2[i]) for i in range(n))
min_difference = total_diff
for i in range(n):
original_value = nums1[i]
for j in range(n):
if i != j:
nums1[i] = nums1[j]
new_diff = sum(abs(nums1[k] - nums2[k]) for k in range(n))
min_difference = min(min_difference, new_diff)
nums1[i] = original_value
return min_difference % MODfunction minAbsoluteSumDiff(nums1, nums2) {
const MOD = 1000000007;
const n = nums1.length;
let totalDiff = 0;
for (let i = 0; i < n; i++) {
totalDiff += Math.abs(nums1[i] - nums2[i]);
}
let minDiff = totalDiff;
for (let i = 0; i < n; i++) {
const originalValue = nums1[i];
for (let j = 0; j < n; j++) {
if (i !== j) {
nums1[i] = nums1[j];
let newDiff = 0;
for (let k = 0; k < n; k++) {
newDiff += Math.abs(nums1[k] - nums2[k]);
}
minDiff = Math.min(minDiff, newDiff);
}
}
nums1[i] = originalValue;
}
return minDiff % MOD;
}This solution iterates through each index of nums1 and considers replacing the value with every other potential value from nums1. After each potential replacement, it recalculates the whole sum of absolute differences.
Time complexity: O(n^2)
Space complexity: O(1) (ignoring input size)
Approach 2: Optimized Approach using Binary Search
This approach aims to minimize the maximum individual absolute difference by using binary search. The idea is to pre-sort nums1 and for each element in nums2, find the closest element in nums1 to minimize the absolute difference. Sorting and using a binary search allows this approach to efficiently handle large input sizes, bringing down the time complexity from O(n^2) to O(n log n).
from bisect import bisect_left
def minAbsoluteSumDiff(nums1, nums2):
MOD = 10**9 + 7
n = len(nums1)
nums1_sorted = sorted(nums1)
total_diff = sum(abs(nums1[i] - nums2[i]) for i in range(n))
max_improvement = 0
for i in range(n):
current_diff = abs(nums1[i] - nums2[i])
idx = bisect_left(nums1_sorted, nums2[i])
if idx < n:
max_improvement = max(max_improvement, current_diff - abs(nums1_sorted[idx] - nums2[i]))
if idx > 0:
max_improvement = max(max_improvement, current_diff - abs(nums1_sorted[idx-1] - nums2[i]))
return (total_diff - max_improvement) % MODfunction minAbsoluteSumDiff(nums1, nums2) {
const MOD = 1e9 + 7;
const n = nums1.length;
const sortedNums1 = [...nums1].sort((a, b) => a - b);
let totalDiff = 0;
for (let i = 0; i < n; i++) {
totalDiff += Math.abs(nums1[i] - nums2[i]);
}
let maxImprovement = 0;
for (let i = 0; i < n; i++) {
const currentDiff = Math.abs(nums1[i] - nums2[i]);
const idx = binarySearch(sortedNums1, nums2[i]);
if (idx < n) {
maxImprovement = Math.max(maxImprovement, currentDiff - Math.abs(sortedNums1[idx] - nums2[i]));
}
if (idx > 0) {
maxImprovement = Math.max(maxImprovement, currentDiff - Math.abs(sortedNums1[idx - 1] - nums2[i]));
}
}
return (totalDiff - maxImprovement) % MOD;
function binarySearch(arr, x) {
let left = 0, right = arr.length;
while (left < right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] < x) left = mid + 1;
else right = mid;
}
return left;
}
}This implementation first calculates the total sum difference. It then finds the optimal replacement for each element using binary search on the sorted array nums1_sorted to find the closest elements to those in nums2, thus minimizing the absolute difference.
Time complexity: O(n log n)
Space complexity: O(n) for sorting
Approach 3: Sorting + Binary Search
According to the problem, we can first calculate the absolute difference sum of nums1 and nums2 without any replacements, denoted as s.
Next, we enumerate each element nums1[i] in nums1, replacing it with the element closest to nums2[i] that also exists in nums1. Therefore, before the enumeration, we can make a copy of nums1, resulting in the array nums, and sort nums. Then, we perform a binary search in nums for the element closest to nums2[i], denoted as nums[j], and calculate |nums1[i] - nums2[i]| - |nums[j] - nums2[i]|, updating the maximum value of the difference mx.
Finally, we subtract mx from s, which is the answer. Note the modulus operation.
The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the length of the array nums1.
class Solution {
public int minAbsoluteSumDiff(int[] nums1, int[] nums2) {
final int mod = (int) 1e9 + 7;
int[] nums = nums1.clone();
Arrays.sort(nums);
int s = 0, n = nums.length;
for (int i = 0; i < n; ++i) {
s = (s + Math.abs(nums1[i] - nums2[i])) % mod;
}
int mx = 0;
for (int i = 0; i < n; ++i) {
int d1 = Math.abs(nums1[i] - nums2[i]);
int d2 = 1 << 30;
int j = search(nums, nums2[i]);
if (j < n) {
d2 = Math.min(d2, Math.abs(nums[j] - nums2[i]));
}
if (j > 0) {
d2 = Math.min(d2, Math.abs(nums[j - 1] - nums2[i]));
}
mx = Math.max(mx, d1 - d2);
}
return (s - mx + mod) % mod;
}
private int search(int[] nums, int x) {
int left = 0, right = nums.length;
while (left < right) {
int mid = (left + right) >>> 1;
if (nums[mid] >= x) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}class Solution {
public:
int minAbsoluteSumDiff(vector<int>& nums1, vector<int>& nums2) {
const int mod = 1e9 + 7;
vector<int> nums(nums1);
sort(nums.begin(), nums.end());
int s = 0, n = nums.size();
for (int i = 0; i < n; ++i) {
s = (s + abs(nums1[i] - nums2[i])) % mod;
}
int mx = 0;
for (int i = 0; i < n; ++i) {
int d1 = abs(nums1[i] - nums2[i]);
int d2 = 1 << 30;
int j = lower_bound(nums.begin(), nums.end(), nums2[i]) - nums.begin();
if (j < n) {
d2 = min(d2, abs(nums[j] - nums2[i]));
}
if (j) {
d2 = min(d2, abs(nums[j - 1] - nums2[i]));
}
mx = max(mx, d1 - d2);
}
return (s - mx + mod) % mod;
}
};function minAbsoluteSumDiff(nums1: number[], nums2: number[]): number {
const mod = 10 ** 9 + 7;
const nums = [...nums1];
nums.sort((a, b) => a - b);
const n = nums.length;
let s = 0;
for (let i = 0; i < n; ++i) {
s = (s + Math.abs(nums1[i] - nums2[i])) % mod;
}
let mx = 0;
for (let i = 0; i < n; ++i) {
const d1 = Math.abs(nums1[i] - nums2[i]);
let d2 = 1 << 30;
let j = search(nums, nums2[i]);
if (j < n) {
d2 = Math.min(d2, Math.abs(nums[j] - nums2[i]));
}
if (j) {
d2 = Math.min(d2, Math.abs(nums[j - 1] - nums2[i]));
}
mx = Math.max(mx, d1 - d2);
}
return (s - mx + mod) % mod;
}
function search(nums: number[], x: number): number {
let left = 0;
let right = nums.length;
while (left < right) {
const mid = (left + right) >> 1;
if (nums[mid] >= x) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}func minAbsoluteSumDiff(nums1 []int, nums2 []int) int {
n := len(nums1)
nums := make([]int, n)
copy(nums, nums1)
sort.Ints(nums)
s, mx := 0, 0
const mod int = 1e9 + 7
for i, a := range nums1 {
b := nums2[i]
s = (s + abs(a-b)) % mod
}
for i, a := range nums1 {
b := nums2[i]
d1, d2 := abs(a-b), 1<<30
j := sort.SearchInts(nums, b)
if j < n {
d2 = min(d2, abs(nums[j]-b))
}
if j > 0 {
d2 = min(d2, abs(nums[j-1]-b))
}
mx = max(mx, d1-d2)
}
return (s - mx + mod) % mod
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time complexity: |
| Optimized Approach using Binary Search | Time complexity: |
| Sorting + Binary Search | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Replacement | O(n^2) | O(1) | Useful for understanding the replacement logic or when input size is very small |
| Sorted Array + Binary Search | O(n log n) | O(n) | General case and interview solution where fast nearest-value lookup is required |
Frequently asked questions
Is Minimum Absolute Sum Difference easy or hard?
Minimum Absolute Sum Difference is rated Medium on LeetCode. The brute force idea is straightforward, but identifying that the optimal replacement must be the closest value to nums2[i] requires algorithmic insight and knowledge of binary search on sorted data.
Minimum Absolute Sum Difference Python/Java solution
Python and Java implementations typically sort a copy of nums1 and use binary search (bisect in Python or Arrays.binarySearch in Java). For each index, they check the closest candidate values and compute the best reduction in absolute difference. The final answer is taken modulo 1e9+7 as required by the problem.
How to solve Minimum Absolute Sum Difference in O(n log n)?
Sort a copy of nums1 and compute the initial total absolute difference. For each index i, use binary search to find the closest value in the sorted array to nums2[i]. Calculate the potential improvement from replacing nums1[i] and track the maximum reduction. Subtract that reduction from the original sum.
What is the best approach for Minimum Absolute Sum Difference?
The optimal approach sorts a copy of nums1 and uses binary search to find the closest value to nums2[i] for each index. This lets you compute the maximum possible reduction in absolute difference from a single replacement. The algorithm runs in O(n log n) time due to sorting and binary searches.
Is Minimum Absolute Sum Difference asked at Google/Amazon/Meta?
Minimum Absolute Sum Difference is a typical medium-level array and binary search problem seen in interviews at companies like Amazon, Google, and other large tech firms. It tests understanding of greedy improvement, sorted structures, and efficient search techniques.
What data structure is used in Minimum Absolute Sum Difference?
The optimized solution relies on a sorted array structure that supports binary search. Some implementations also use ordered sets or balanced trees to find the closest value efficiently. The core idea is performing nearest-value queries in O(log n) time.
What is the time complexity of Minimum Absolute Sum Difference?
The optimized solution runs in O(n log n) time and O(n) space. Sorting nums1 takes O(n log n), and each of the n iterations performs a binary search in O(log n). A naive brute force replacement approach would take O(n^2) time.