{x}
blog image

Minimum Absolute Sum Difference

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.length
  • n == nums2.length
  • 1 <= n <= 105
  • 1 <= nums1[i], nums2[i] <= 105

Solution Explanation: Minimum Absolute Sum Difference

This problem asks us to find the minimum absolute sum difference between two arrays, nums1 and nums2, after replacing at most one element in nums1. The solution uses a combination of sorting and binary search for optimal efficiency.

Approach:

  1. Calculate Initial Sum: First, we calculate the total absolute sum difference between nums1 and nums2 without any replacements. This is our starting point.

  2. Sort nums1: We create a sorted copy of nums1 (let's call it sortedNums1). This sorted array is crucial for efficient searching later.

  3. Iterate and Optimize: We iterate through each element pair (nums1[i], nums2[i]). For each pair:

    • We find the element in sortedNums1 that minimizes the absolute difference with nums2[i]. This is done efficiently using binary search (bisect_left in Python, lower_bound in C++, sort.SearchInts in Go, or a custom binary search function in other languages). The binary search allows us to find the closest element in O(log n) time.
    • We calculate the difference between the original absolute difference (abs(nums1[i] - nums2[i])) and the new absolute difference (abs(closest_element - nums2[i])). This represents the potential reduction in the total sum if we replace nums1[i] with the closest element.
    • We track the maximum potential reduction (mx).

  4. Final Result: The minimum absolute sum difference after potentially replacing one element is the initial sum minus the maximum potential reduction (s - mx). We use the modulo operator to handle potential large numbers.

Time Complexity Analysis:

  • Sorting nums1: O(n log n)
  • Iterating through nums1 and performing binary search for each element: O(n log n)

Therefore, the overall time complexity is O(n log n), dominated by the sorting and binary search operations.

Space Complexity Analysis:

  • We create a sorted copy of nums1: O(n)

Thus, the space complexity is O(n).

Code Examples (Python, Java, C++, Go, TypeScript, JavaScript):

The provided code snippets in different languages implement this approach. They all follow the same algorithmic steps: calculate the initial sum, sort nums1, iterate, use binary search for optimization, and calculate the final result. Note the slight variations in how binary search is implemented across different languages. The comments within the code further explain the individual steps.

Example (Python):

import bisect
from typing import List
 
class Solution:
    def minAbsoluteSumDiff(self, nums1: List[int], nums2: List[int]) -> int:
        mod = 10**9 + 7
        nums = sorted(nums1)
        s = sum(abs(a - b) for a, b in zip(nums1, nums2)) % mod
        mx = 0
        for a, b in zip(nums1, nums2):
            d1, d2 = abs(a - b), float('inf')
            i = bisect_left(nums, b)
            if i < len(nums):
                d2 = min(d2, abs(nums[i] - b))
            if i:
                d2 = min(d2, abs(nums[i - 1] - b))
            mx = max(mx, d1 - d2)
        return (s - mx + mod) % mod

The other language examples follow a similar structure, adapting the syntax and libraries to their respective languages. The core algorithm remains consistent.