1818. Minimum Absolute Sum Difference #

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:

• 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 <= 10^5
• 1 <= nums1[i], nums2[i] <= 10^5

Problem Summary #

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 all |nums1[i] - nums2[i]| (0 <= i < n) (0-indexed). You can choose any one element from nums1 to replace at most one element in nums1 to minimize the absolute sum difference. After replacing at most one element in array nums1, return the minimum absolute sum difference. Since the answer may be large, return it modulo 10^9 + 7.

Solution Ideas #

• If no element is changed, the absolute sum difference is \( \sum \left | nums1[i] - nums2[i] \right | \) . If one element is changed, then the absolute sum difference is \[ \begin{aligned}&\sum \left | nums1[i] - nums2[i] \right | - \left ( \left | nums1[i] - nums2[i] \right | - \left | nums1[j] - nums2[i] \right |\right )\\= &\sum \left | nums1[i] - nums2[i] \right | - \Delta \end{aligned} \]

  The problem asks to return the minimum absolute sum difference, which is to find the maximum value of \(\Delta \) . Brute-force enumerate the pairwise differences between nums1 and nums2, find maxdiff, which is the maximum value of \(\Delta \) , and the solution to this problem is obtained.

Code #

package leetcode

func minAbsoluteSumDiff(nums1 []int, nums2 []int) int {
	diff := 0
	maxDiff := 0
	for i, n2 := range nums2 {
		d := abs(nums1[i] - n2)
		diff += d
		if maxDiff < d {
			t := 100001
			for _, n1 := range nums1 {
				maxDiff = max(maxDiff, d-min(t, abs(n1-n2)))
			}
		}
	}
	return (diff - maxDiff) % (1e9 + 7)
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func abs(a int) int {
	if a > 0 {
		return a
	}
	return -a
}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}