Formatted question description: https://leetcode.ca/all/1818.html

1818. Minimum Absolute Sum Difference

Level

Medium

Description

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 10^9 + 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

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

Solution

Use a tree set to store the numbers in nums1, and calculate the original absolute sum difference. Then for each 0 <= i < n, replace nums1[i] with the two closest values of nums2[i] and calculate the new absolute sum difference. Maintain the minimum absolute sum difference during the process. Finally, return the minimum absolute sum difference.

class Solution {
    public int minAbsoluteSumDiff(int[] nums1, int[] nums2) {
        final int MODULO = 1000000007;
        TreeSet<Integer> set = new TreeSet<Integer>();
        long sum = 0;
        int length = nums1.length;
        for (int i = 0; i < length; i++) {
            sum += (long) Math.abs(nums1[i] - nums2[i]);
            set.add(nums1[i]);
        }
        long minSum = sum;
        for (int i = 0; i < length; i++) {
            int num2 = nums2[i];
            Integer newNumFloor = set.floor(num2), newNumCeiling = set.ceiling(num2);
            long curSum = sum - (long) Math.abs(nums1[i] - nums2[i]);
            if (newNumFloor != null) {
                long curSumFloor = curSum + (long) Math.abs(newNumFloor - nums2[i]);
                minSum = Math.min(minSum, curSumFloor);
            }
            if (newNumCeiling != null) {
                long curSumCeiling = curSum + (long) Math.abs(newNumCeiling - nums2[i]);
                minSum = Math.min(minSum, curSumCeiling);
            }
        }
        return (int) (minSum % MODULO);
    }
}

############

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;
    }
}

// OJ: https://leetcode.com/problems/minimum-absolute-sum-difference/
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
    int minAbsoluteSumDiff(vector<int>& A, vector<int>& B) {
        long sum = 0, mod = 1e9 + 7, N = A.size();
        set<int> s(begin(A), end(A));
        for (int i = 0; i < N; ++i) sum += abs((long)A[i] - B[i]);
        long ans = sum;
        for (int i = 0; i < N; ++i) {
            int diff = abs((long)A[i] - B[i]);
            auto it = s.lower_bound(B[i]);
            if (it != s.end()) {
                ans = min(ans, sum - diff + abs((long)B[i] - *it));
            }
            if (it != s.begin()) {
                ans = min(ans, sum - diff + abs((long)B[i] - *prev(it)));
            }
        }
        return ans % mod;
    }
};

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), 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

############

# 1818. Minimum Absolute Sum Difference
# https://leetcode.com/problems/minimum-absolute-sum-difference

class Solution:
    def minAbsoluteSumDiff(self, nums1: List[int], nums2: List[int]) -> int:
        M = 10 ** 9 + 7        
        n = len(nums1)
        total = sum(abs(a-b) for a, b in zip(nums1, nums2))
        
        sl = list(sorted(nums1))
        res = float('inf')
        
        for i, (a,b) in enumerate(zip(nums1, nums2)):
            diff = abs(a - b)
            idx = bisect.bisect_left(sl, b)
            
            if idx > 0:
                res = min(res, total - diff + abs(b - sl[idx-1]))    
            
            if idx < n:
                res = min(res, total - diff + abs(b - sl[idx]))
                    
        return res % M

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.Search(n, func(k int) bool { return nums[k] >= 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 max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

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

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

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;
}

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var minAbsoluteSumDiff = function (nums1, nums2) {
    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, x) {
    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;
}

1818 - Minimum Absolute Sum Difference

1818. Minimum Absolute Sum Difference

Level

Description

Solution

All Problems

All Solutions

Welcome to Subscribe On Youtube

1818. Minimum Absolute Sum Difference

Level

Description

Solution

All Problems

All Solutions