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:
x if x >= 0, or-x if x < 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] <= 105Problem 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.
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.
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.
Python
JavaScript
Time complexity: O(n^2)
Space complexity: O(1) (ignoring input size)
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).
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.
Python
JavaScript
Time complexity: O(n log n)
Space complexity: O(n) for sorting
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.
Python
Java
C++
Go
TypeScript
JavaScript
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time complexity: |
| Optimized Approach using Binary Search | Time complexity: |
| Sorting + Binary Search | — |
| 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 |
LeetCode 1818. Minimum Absolute Sum Difference | Medium | 🏆 Weekly Contest 235 | Algorithm Explained • Cherry Coding [IIT-G] • 9,026 views views
Watch 7 more video solutions →Practice Minimum Absolute Sum Difference with our built-in code editor and test cases.
Practice on FleetCode