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 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
n == nums1.length
n == nums2.length
1 <= n <= 105
1 <= nums1[i], nums2[i] <= 105
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
