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] <= 105The 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.
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.
JavaScript
Time complexity: O(n log n)
Space complexity: O(n) for sorting
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time complexity: |
| Optimized Approach using Binary Search | Time complexity: |
Dp 16. Partition A Set Into Two Subsets With Minimum Absolute Sum Difference | DP on Subsequences • take U forward • 340,429 views views
Watch 9 more video solutions →Practice Minimum Absolute Sum Difference with our built-in code editor and test cases.
Practice on FleetCode