LeetCode 1818: Minimum Absolute Sum Difference

Explanation

To solve this problem, we can iterate through each element in nums1 and calculate the absolute difference with the corresponding element in nums2. We will keep track of the maximum possible reduction in the absolute sum difference by replacing any element in nums1 with another element in nums1. We can find this maximum reduction by sorting nums1 and nums2 and calculating the absolute difference between elements at the same index.

Algorithm

1. Calculate the initial absolute sum difference of nums1 and nums2.
2. Iterate through each element x in nums1 and calculate the absolute difference diff with the corresponding element in nums2.
3. For each x, find the element y in nums1 such that replacing x with y reduces the absolute sum difference the most.
4. Update the maximum reduction in absolute sum difference.
5. Return the minimum absolute sum difference modulo 10^9 + 7.

Time Complexity

The time complexity of this algorithm is O(n log n) due to sorting the arrays nums1 and nums2.

Space Complexity

The space complexity of this algorithm is O(n) to store the absolute differences and the sorted arrays.

class Solution {
    public int minAbsoluteSumDiff(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int[] sortedNums1 = nums1.clone();
        Arrays.sort(sortedNums1);
        
        int sumDiff = 0;
        int maxReduction = 0;
        
        for (int i = 0; i < n; i++) {
            int diff = Math.abs(nums1[i] - nums2[i]);
            sumDiff = (sumDiff + diff) % 1000000007;
            
            int j = Arrays.binarySearch(sortedNums1, nums2[i]);
            if (j < 0) {
                j = -(j + 1);
            }
            
            if (j < n) {
                maxReduction = Math.max(maxReduction, diff - Math.abs(sortedNums1[j] - nums2[i]));
            }
            
            if (j > 0) {
                maxReduction = Math.max(maxReduction, diff - Math.abs(sortedNums1[j - 1] - nums2[i]));
            }
        }
        
        return (sumDiff - maxReduction + 1000000007) % 1000000007;
    }
}