We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Absolute Sum Difference

Difficulty: Medium

Problem 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. 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.

Key Insights

  • The absolute sum difference can be calculated directly by summing the absolute differences for all indices.
  • Replacing one element in nums1 can potentially reduce the absolute sum difference if it aligns better with the corresponding element in nums2.
  • Using binary search can help efficiently find the best candidate for replacement in nums1 to minimize the absolute sum difference.
  • The overall approach involves calculating the initial absolute sum difference and then checking the effect of replacements.

Space and Time Complexity

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

Solution

To solve the problem, we first calculate the initial absolute sum difference between nums1 and nums2. Then, for each element in nums2, we use binary search to find the closest element in nums1 that can be used for replacement. The goal is to minimize the absolute difference for that index by replacing nums1[i] with the closest value found. Finally, we return the minimum absolute sum difference modulo 10^9 + 7.

Code Solutions

def minAbsoluteSumDiff(nums1, nums2):
    MOD = 10**9 + 7
    n = len(nums1)
    
    # Calculate the initial absolute sum difference
    initial_sum = sum(abs(a - b) for a, b in zip(nums1, nums2))
    
    # Sort nums1 for binary search
    sorted_nums1 = sorted(nums1)
    
    max_improvement = 0
    
    for b in nums2:
        # Binary search for the closest element in nums1
        left, right = 0, n - 1
        while left <= right:
            mid = (left + right) // 2
            if sorted_nums1[mid] < b:
                left = mid + 1
            else:
                right = mid - 1
        
        # Check the closest values
        if left < n:
            max_improvement = max(max_improvement, abs(b - sorted_nums1[left]) - abs(b - nums1[nums2.index(b)]))
        if right >= 0:
            max_improvement = max(max_improvement, abs(b - sorted_nums1[right]) - abs(b - nums1[nums2.index(b)]))
    
    # Return the minimum absolute sum difference
    return (initial_sum - max_improvement) % MOD
← Back to All Questions