1818. Minimum Absolute Sum Difference LeetCode Solution

In this guide, you will get 1818. Minimum Absolute Sum Difference LeetCode Solution with the best time and space complexity. The solution to Minimum Absolute Sum Difference problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Minimum Absolute Sum Difference solution in C++
Minimum Absolute Sum Difference solution in Java
Minimum Absolute Sum Difference solution in Python
Additional Resources

1818. Minimum Absolute Sum Difference LeetCode Solution image

Problem Statement of 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 = 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

Complexity Analysis

Time Complexity: O(n\log n)
Space Complexity: O(n)

1818. Minimum Absolute Sum Difference LeetCode Solution in C++

class Solution {
 public:
  int minAbsoluteSumDiff(vector<int>& nums1, vector<int>& nums2) {
    constexpr int kMod = 1'000'000'007;
    long sumDiff = 0;
    long maxDecrement = 0;
    set<int> sorted(nums1.begin(), nums1.end());

    for (int i = 0; i < nums1.size(); ++i) {
      const long currDiff = abs(nums1[i] - nums2[i]);
      sumDiff += currDiff;
      const auto it = sorted.lower_bound(nums2[i]);
      if (it != sorted.begin())
        maxDecrement = max(maxDecrement, currDiff - abs(*prev(it) - nums2[i]));
      if (it != sorted.end())
        maxDecrement = max(maxDecrement, currDiff - abs(*it - nums2[i]));
    }

    return (sumDiff - maxDecrement) % kMod;
  }
};
/* code provided by PROGIEZ */

1818. Minimum Absolute Sum Difference LeetCode Solution in Java

class Solution {
  public int minAbsoluteSumDiff(int[] nums1, int[] nums2) {
    final int kMod = 1_000_000_007;
    long sumDiff = 0;
    long maxDecrement = 0;
    TreeSet<Integer> sorted = new TreeSet<>();

    for (final int num : nums1)
      sorted.add(num);

    for (int i = 0; i < nums1.length; ++i) {
      final long currDiff = (long) Math.abs(nums1[i] - nums2[i]);
      sumDiff += currDiff;
      Integer ceiling = sorted.ceiling(nums2[i]);
      Integer floor = sorted.floor(nums2[i]);
      if (ceiling != null)
        maxDecrement = Math.max(maxDecrement, currDiff - (long) Math.abs(ceiling - nums2[i]));
      if (floor != null)
        maxDecrement = Math.max(maxDecrement, currDiff - (long) Math.abs(floor - nums2[i]));
    }

    return (int) ((sumDiff - maxDecrement) % kMod);
  }
}
// code provided by PROGIEZ

1818. Minimum Absolute Sum Difference LeetCode Solution in Python

class Solution:
  def minAbsoluteSumDiff(self, nums1: list[int], nums2: list[int]) -> int:
    ans = math.inf
    diffs = [abs(a - b) for a, b in zip(nums1, nums2)]
    sumDiff = sum(diffs)

    nums1.sort()

    for num, diff in zip(nums2, diffs):
      i = bisect.bisect_left(nums1, num)
      if i > 0:
        ans = min(ans, sumDiff - diff + abs(num - nums1[i - 1]))
      if i < len(nums1):
        ans = min(ans, sumDiff - diff + abs(num - nums1[i]))

    return ans % int(1e9 + 7)
 # code by PROGIEZ