LeetCode 1818 - Minimum Absolute Sum Difference

The problem gives two arrays of positive integers, nums1 and nums2, both of equal length n. The goal is to calculate the absolute sum difference between these arrays, which is the sum of the absolute differences at each index: |nums1[i] - nums2[i]|.

leetcodemediumarraybinary-searchsortingordered-set

LeetCode Problem 1818

Difficulty: 🟡 Medium
Topics: Array, Binary Search, Sorting, Ordered Set

Solution

Problem Understanding

The problem gives two arrays of positive integers, nums1 and nums2, both of equal length n. The goal is to calculate the absolute sum difference between these arrays, which is the sum of the absolute differences at each index: |nums1[i] - nums2[i]|. You are allowed to replace at most one element in nums1 with any other element from nums1 to minimize this sum. The result must be returned modulo 10^9 + 7.

In simpler terms, we are trying to make the two arrays as "close" as possible by changing at most one element in nums1, picking the optimal replacement to reduce the sum of absolute differences.

The constraints indicate that n can be up to 10^5 and values in the arrays up to 10^5. This implies that a naive solution that tries every possible replacement for every index will be too slow, as it would be roughly O(n²) in time complexity.

Important edge cases to consider include arrays that are already equal, arrays where replacing any element cannot reduce the sum significantly, and arrays with maximum possible values.

Approaches

Brute Force

A naive approach is to consider replacing each element in nums1 with every other element in nums1 and calculate the resulting absolute sum difference. You would track the minimum sum observed across all replacements. While correct, this approach has a time complexity of O(n²), which is infeasible for n = 10^5. It also uses O(1) additional space, but the time cost dominates.

Optimal Approach

The key observation is that, for each nums2[i], the best candidate replacement in nums1 is the element closest to nums2[i] because it minimizes |nums1[j] - nums2[i]|. To efficiently find this, we can sort a copy of nums1 and use binary search to find the closest element to nums2[i]. For each index, we compute the potential improvement in the absolute difference if we replace the current nums1[i] with this closest element. We then take the maximum improvement across all indices and subtract it from the total sum.

This approach reduces the complexity significantly because sorting and binary search are efficient: sorting takes O(n log n), and for each index, binary search takes O(log n).

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Try all possible replacements for each element
Optimal O(n log n) O(n) Sort nums1 and use binary search for closest element to minimize sum

Algorithm Walkthrough

  1. Compute the initial absolute sum difference without any replacements.
  2. Create a sorted copy of nums1 to facilitate efficient closest-value searches.
  3. Initialize a variable max_improvement to track the maximum reduction possible by replacing a single element.
  4. For each index i:

a. Compute the current difference: diff = |nums1[i] - nums2[i]|.

b. Use binary search on the sorted nums1 to find the closest element to nums2[i].

c. Compute the new difference if replaced with the closest element.

d. Update max_improvement if the difference is reduced more than previously observed. 5. Subtract max_improvement from the initial sum to get the minimum possible sum. 6. Return the result modulo 10^9 + 7.

Why it works: Each element in nums2 contributes independently to the sum, and replacing at most one element in nums1 means we only need to find the single replacement that maximizes reduction. By always choosing the closest candidate using binary search, we guarantee the optimal local improvement, and checking all indices ensures the global optimum is found.

Python Solution

from bisect import bisect_left
from typing import List

class Solution:
    def minAbsoluteSumDiff(self, nums1: List[int], nums2: List[int]) -> int:
        MOD = 10**9 + 7
        n = len(nums1)
        sorted_nums1 = sorted(nums1)
        
        total_diff = sum(abs(a - b) for a, b in zip(nums1, nums2))
        max_improvement = 0
        
        for i in range(n):
            original_diff = abs(nums1[i] - nums2[i])
            
            # Binary search for closest value to nums2[i]
            idx = bisect_left(sorted_nums1, nums2[i])
            closest_diff = original_diff
            
            if idx < n:
                closest_diff = min(closest_diff, abs(sorted_nums1[idx] - nums2[i]))
            if idx > 0:
                closest_diff = min(closest_diff, abs(sorted_nums1[idx - 1] - nums2[i]))
            
            max_improvement = max(max_improvement, original_diff - closest_diff)
        
        return (total_diff - max_improvement) % MOD

This implementation first calculates the initial sum of absolute differences. It then iterates through each element, using binary search on the sorted copy of nums1 to find the closest replacement that could minimize the difference. max_improvement tracks the maximal reduction possible from a single replacement.

Go Solution

import (
    "sort"
    "math"
)

func minAbsoluteSumDiff(nums1 []int, nums2 []int) int {
    const MOD = 1_000_000_007
    n := len(nums1)
    sortedNums1 := append([]int(nil), nums1...)
    sort.Ints(sortedNums1)
    
    totalDiff := 0
    maxImprovement := 0
    
    for i := 0; i < n; i++ {
        originalDiff := int(math.Abs(float64(nums1[i] - nums2[i])))
        totalDiff += originalDiff
        
        idx := sort.SearchInts(sortedNums1, nums2[i])
        closestDiff := originalDiff
        
        if idx < n {
            d := int(math.Abs(float64(sortedNums1[idx] - nums2[i])))
            if d < closestDiff {
                closestDiff = d
            }
        }
        if idx > 0 {
            d := int(math.Abs(float64(sortedNums1[idx-1] - nums2[i])))
            if d < closestDiff {
                closestDiff = d
            }
        }
        improvement := originalDiff - closestDiff
        if improvement > maxImprovement {
            maxImprovement = improvement
        }
    }
    
    return (totalDiff - maxImprovement) % MOD
}

The Go implementation mirrors the Python solution, using the built-in sort and binary search. We explicitly cast to float64 when using math.Abs and cast back to int to handle differences correctly. The logic for computing maxImprovement and applying the modulo remains the same.

Worked Examples

Example 1: nums1 = [1,7,5], nums2 = [2,3,5]

Initial differences: [1,4,0], total sum = 5.

Binary search for each element:

  • i = 0: closest to 2 is 1 -> improvement = 0
  • i = 1: closest to 3 is 1 or 5 -> best improvement = 4 - 2 = 2
  • i = 2: closest to 5 is 5 -> improvement = 0

Maximum improvement = 2

Minimum sum = 5 - 2 = 3

Example 2: nums1 = [2,4,6,8,10], nums2 = [2,4,6,8,10]

Initial differences: [0,0,0,0,0], total sum = 0

Maximum improvement = 0

Minimum sum = 0

Example 3: nums1 = [1,10,4,4,2,7], nums2 = [9,3,5,1,7,4]

Initial differences: [8,7,1,3,5,3], total sum = 27

  • i = 0: closest to 9 is 10 -> improvement = 8 - 1 = 7
  • i = 1: closest to 3 is 4 -> improvement = 7 - 1 = 6
  • i = 2: closest to 5 is 4 -> improvement = 1 - 1 = 0
  • ...

Maximum improvement = 7

Minimum sum = 27 - 7 = 20

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting nums1 takes O(n log n) and binary search for each of n elements takes O(log n)
Space O(n) A sorted copy of nums1 is maintained

The algorithm efficiently handles large arrays by using sorting and binary search rather than brute-force replacements.

Test Cases

# Provided examples
assert Solution().minAbsoluteSumDiff([1,7,5], [2,3,5]) == 3  # Example 1
assert Solution().minAbsoluteSumDiff([2,4,6,8,10], [2,4,6,8,10]) == 0  # Example 2
assert Solution().minAbsoluteSumDiff([1,10,4,4,2,7], [9,3,5,1,7,4]) ==