Scale Engineer

Minimum Absolute Sum Difference

Med
#1662Time: O(n^2), where n is the length of the arrays. The nested loops dominate the runtime, iterating n*n times.Space: O(1), as we only use a constant amount of extra space for variables.
Algorithms
Binary SearchSorting
Data structures
ArrayOrdered Set

Prompt

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 (0-indexed).

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 109 + 7.

|x| is defined as:

  • x if x >= 0, or
  • -x if x < 0.

 

Example 1:

|1-2| + (|1-3| or |5-3|) + |5-5| =

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:

|10-9| + |10-3| + |4-5| + |4-1| + |2-7| + |7-4| = 20

 

Constraints:

  • n == nums1.length
  • n == nums2.length
  • 1 <= n <= 105
  • 1 <= nums1[i], nums2[i] <= 105

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves a straightforward, exhaustive search. For each element in nums1, we consider replacing it with every other element from nums1 (including itself). We calculate the total absolute sum difference for each possible single replacement and find the minimum among them. This method guarantees finding the optimal solution but is computationally expensive.

Algorithm

  • Calculate the initial sum S = sum(|nums1[i] - nums2[i]|).
  • Initialize maxReduction = 0.
  • Use a nested loop. The outer loop iterates through each index i of nums1 (the element to be replaced).
  • The inner loop iterates through each index j of nums1 (the replacement element).
  • Inside the inner loop, calculate the potential reduction: reduction = |nums1[i] - nums2[i]| - |nums1[j] - nums2[i]|.
  • Update maxReduction = max(maxReduction, reduction).
  • The final minimum sum is S - maxReduction.
  • Return the result modulo 10^9 + 7.

Walkthrough

The algorithm begins by calculating the initial absolute sum difference, S = sum(|nums1[i] - nums2[i]|). The goal is to find the single replacement that provides the maximum possible reduction to this sum. We iterate through every element nums1[i] as a candidate to be replaced. For each nums1[i], we then iterate through every element nums1[j] as a potential new value. For each such potential replacement, we calculate the change in the difference at index i, which is |nums1[j] - nums2[i]| - |nums1[i] - nums2[i]|. We are interested in the most negative change, which corresponds to the maximum reduction. We keep track of the maxReduction found across all possibilities. The final answer is the initialSum - maxReduction. All sum calculations are performed using long to prevent overflow, and the final result is returned modulo 10^9 + 7.

class Solution {    public int minAbsoluteSumDiff(int[] nums1, int[] nums2) {        int n = nums1.length;        long initialSum = 0;        int MOD = 1_000_000_007;         for (int i = 0; i < n; i++) {            initialSum += Math.abs(nums1[i] - nums2[i]);        }         if (initialSum == 0) {            return 0;        }         long maxReduction = 0;        for (int i = 0; i < n; i++) {            int originalDiff = Math.abs(nums1[i] - nums2[i]);            // Try replacing nums1[i] with every element from nums1            for (int j = 0; j < n; j++) {                int newDiff = Math.abs(nums1[j] - nums2[i]);                long currentReduction = originalDiff - newDiff;                if (currentReduction > maxReduction) {                    maxReduction = currentReduction;                }            }        }         long result = (initialSum - maxReduction) % MOD;        return (int) result;    }}

Complexity

Time

O(n^2), where n is the length of the arrays. The nested loops dominate the runtime, iterating n*n times.

Space

O(1), as we only use a constant amount of extra space for variables.

Trade-offs

Pros

  • Conceptually simple and easy to implement.

  • Directly follows the problem definition.

Cons

  • Highly inefficient due to its quadratic time complexity.

  • Will not pass for large inputs, leading to a Time Limit Exceeded (TLE) error.

Solutions

class Solution {public  int minAbsoluteSumDiff(int[] nums1, int[] nums2) {    final int mod = (int)1 e9 + 7;    int[] nums = nums1.clone();    Arrays.sort(nums);    int s = 0, n = nums.length;    for (int i = 0; i < n; ++i) {      s = (s + Math.abs(nums1[i] - nums2[i])) % mod;    }    int mx = 0;    for (int i = 0; i < n; ++i) {      int d1 = Math.abs(nums1[i] - nums2[i]);      int d2 = 1 << 30;      int j = search(nums, nums2[i]);      if (j < n) {        d2 = Math.min(d2, Math.abs(nums[j] - nums2[i]));      }      if (j > 0) {        d2 = Math.min(d2, Math.abs(nums[j - 1] - nums2[i]));      }      mx = Math.max(mx, d1 - d2);    }    return (s - mx + mod) % mod;  }private  int search(int[] nums, int x) {    int left = 0, right = nums.length;    while (left < right) {      int mid = (left + right) >>> 1;      if (nums[mid] >= x) {        right = mid;      } else {        left = mid + 1;      }    }    return left;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem