LeetCode Solutions Blog

Minimum Absolute Sum Difference

Number: 1946

Difficulty: Medium

Paid? No

Companies: Uber

Problem Description

Given two positive integer arrays nums1 and nums2 of the same length, you must minimize the absolute sum difference defined as the sum of |nums1[i] - nums2[i]| over all indices. You are allowed to replace at most one element in nums1 with any other element from nums1 to reduce the overall sum. Return the minimum absolute sum difference after at most one replacement, modulo 10^9 + 7.

Key Insights

Pre-sort a copy of nums1 to enable efficient binary search for the best replacement candidate.
For each pair, compute the original difference and then try to find a candidate in the sorted nums1 that minimizes the absolute difference with nums2[i].
Only one replacement is allowed; therefore, track the maximum improvement achievable.
Use modulo arithmetic to handle large sums.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting and binary search performed for each index. Space Complexity: O(n) for the sorted copy of nums1.

Solution

We first compute the total absolute difference without any replacement. Then, by sorting a copy of nums1, we can perform a binary search for each nums2[i] to find the element in nums1 closest to nums2[i]. This gives the best possible replacement candidate for that index. We calculate the difference improvement for each index and keep track of the maximum improvement found. Finally, subtract the maximum improvement from the original sum and return the result modulo 10^9 + 7.

Code Solutions

# Define the modulo constant
MOD = 10**9 + 7

def minAbsoluteSumDiff(nums1, nums2):
    n = len(nums1)
    # Create a sorted copy of nums1 for binary search
    sorted_nums1 = sorted(nums1)
    
    # Calculate the initial total absolute sum difference
    total_diff = 0
    max_improvement = 0
    
    # Helper function for binary search to find the candidate closest to target
    def findClosest(arr, target):
        left, right = 0, len(arr) - 1
        while left < right:
            mid = (left + right) // 2
            if arr[mid] < target:
                left = mid + 1
            else:
                right = mid
        # At this point, arr[left] is the smallest number >= target,
        # Check left and left-1 (if exists) to choose the best candidate
        best = arr[left]
        if left > 0 and abs(arr[left - 1] - target) < abs(best - target):
            best = arr[left - 1]
        return best

    # Iterate through each index and try to find a replacement that minimizes the difference
    for i in range(n):
        original_diff = abs(nums1[i] - nums2[i])
        total_diff = (total_diff + original_diff) % MOD
        
        # Find candidate in sorted_nums1 closest to nums2[i]
        candidate = findClosest(sorted_nums1, nums2[i])
        new_diff = abs(candidate - nums2[i])
        # Calculate potential improvement
        improvement = original_diff - new_diff
        if improvement > max_improvement:
            max_improvement = improvement
            
    # Final result after applying the best replacement, ensuring non-negative modulo result
    return (total_diff - max_improvement) % MOD

# Example usage:
print(minAbsoluteSumDiff([1,7,5], [2,3,5]))  # Expected output: 3