LeetCode 1818: Minimum Absolute Sum Difference Solution

Master LeetCode problem 1818 (Minimum Absolute Sum Difference), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1818. Minimum Absolute Sum Difference

Medium

Array Binary Search Sorting Ordered Set

Problem Explanation

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

Calculate the initial absolute sum difference of nums1 and nums2.
Iterate through each element x in nums1 and calculate the absolute difference diff with the corresponding element in nums2.
For each x, find the element y in nums1 such that replacing x with y reduces the absolute sum difference the most.
Update the maximum reduction in absolute sum difference.
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.

Solution Code

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

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1818 (Minimum Absolute Sum Difference)?

This page provides optimized solutions for LeetCode problem 1818 (Minimum Absolute Sum Difference) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1818 (Minimum Absolute Sum Difference)?

The time complexity for LeetCode 1818 (Minimum Absolute Sum Difference) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1818 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1818 in Java, C++, or Python.

Back to LeetCode Solutions