# Minimum Absolute Sum Difference
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-absolute-sum-difference)
Canonical: https://scaleengineer.com/dsa/problems/minimum-absolute-sum-difference
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Ordered Set
---
## Problem
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 oneelement 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:**

**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`

**Constraints:**

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

# Approaches
## Brute Force Iteration
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.
**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.
**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.
### Explanation
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`.

```java
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;
    }
}
```
### 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`.

## Optimized Search with Sorting and Binary Search
This approach optimizes the process of finding the best replacement. Instead of a linear scan for each element, we first sort a copy of `nums1`. Then, for each element `nums2[i]`, we can use binary search on the sorted array to efficiently find the value in `nums1` that is closest to `nums2[i]`. This reduces the time to find the best replacement from O(n) to O(log n), making the overall algorithm much faster.
**Time:** O(n log n). Sorting the array takes O(n log n). The main loop runs n times, with each iteration performing a binary search that takes O(log n), resulting in another O(n log n) complexity. Thus, the total time is O(n log n). · **Space:** O(n), for storing the sorted copy of `nums1`. If modifying the input array `nums1` were allowed, this could be reduced to O(log n) or O(1) depending on the sorting algorithm's space complexity.
**Pros:** Efficient, with a time complexity of O(n log n), which is suitable for the given constraints.; Correctly finds the optimal solution.
**Cons:** Requires O(n) extra space to store the sorted copy of the array.; Slightly more complex to implement than the brute-force approach due to the binary search logic.
### Explanation
The strategy is to maximize the reduction `|nums1[i] - nums2[i]| - |replacement - nums2[i]|` for some index `i`. This is equivalent to finding a `replacement` from `nums1` that minimizes `|replacement - nums2[i]|`. To do this efficiently, we first create a sorted copy of `nums1`. After calculating the initial total sum difference, we iterate through the original arrays. For each index `i`, we take `nums2[i]` as a target and use binary search on the sorted `nums1` to find the element(s) closest to it. The closest elements will be the floor and/or ceiling of `nums2[i]` in the sorted array. By comparing `nums2[i]` with these two candidates, we can find the minimum possible new difference `minNewDiff`. The potential reduction for this index is then `|nums1[i] - nums2[i]| - minNewDiff`. We track the maximum such reduction over all `i`. The final answer is the initial sum minus this maximum reduction, modulo `10^9 + 7`.

```java
import java.util.Arrays;

class Solution {
    public int minAbsoluteSumDiff(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int MOD = 1_000_000_007;

        int[] sortedNums1 = nums1.clone();
        Arrays.sort(sortedNums1);

        long initialSum = 0;
        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]);
            int target = nums2[i];

            // Binary search to find the closest element in sortedNums1
            int j = Arrays.binarySearch(sortedNums1, target);
            if (j < 0) {
                j = -(j + 1); // This is the insertion point
            }

            int minNewDiff = Integer.MAX_VALUE;
            
            // Candidate 1: element at or after insertion point (ceiling)
            if (j < n) {
                minNewDiff = Math.min(minNewDiff, Math.abs(sortedNums1[j] - target));
            }
            // Candidate 2: element before insertion point (floor)
            if (j > 0) {
                minNewDiff = Math.min(minNewDiff, Math.abs(sortedNums1[j - 1] - target));
            }
            
            long currentReduction = originalDiff - minNewDiff;
            if (currentReduction > maxReduction) {
                maxReduction = currentReduction;
            }
        }

        long result = initialSum - maxReduction;
        return (int) (result % MOD);
    }
}
```
### Algorithm
- Create a sorted copy of `nums1`, let's call it `sortedNums1`.
- Calculate the initial sum `S = sum(|nums1[i] - nums2[i]|)`.
- Initialize `maxReduction = 0`.
- For each index `i` from `0` to `n-1`:
  - Find the element in `sortedNums1` closest to `nums2[i]` using binary search. This involves checking the elements at the floor and ceiling of `nums2[i]`'s position in `sortedNums1`.
  - Let this minimum possible difference be `minNewDiff`.
  - Calculate the potential reduction: `reduction = |nums1[i] - nums2[i]| - minNewDiff`.
  - Update `maxReduction = max(maxReduction, reduction)`.
- The final minimum sum is `S - maxReduction`.
- Return the result modulo `10^9 + 7`.

# Solutions
### Java

```java
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;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} nums1 * @param {number[]} nums2 * @return {number} */ var minAbsoluteSumDiff =
  function (nums1, nums2) {
    const mod = 10 ** 9 + 7;
    const nums = [...nums1];
    nums.sort((a, b) => a - b);
    const n = nums.length;
    let s = 0;
    for (let i = 0; i < n; ++i) {
      s = (s + Math.abs(nums1[i] - nums2[i])) % mod;
    }
    let mx = 0;
    for (let i = 0; i < n; ++i) {
      const d1 = Math.abs(nums1[i] - nums2[i]);
      let d2 = 1 << 30;
      let j = search(nums, nums2[i]);
      if (j < n) {
        d2 = Math.min(d2, Math.abs(nums[j] - nums2[i]));
      }
      if (j) {
        d2 = Math.min(d2, Math.abs(nums[j - 1] - nums2[i]));
      }
      mx = Math.max(mx, d1 - d2);
    }
    return (s - mx + mod) % mod;
  };
function search(nums, x) {
  let left = 0;
  let right = nums.length;
  while (left < right) {
    const mid = (left + right) >> 1;
    if (nums[mid] >= x) {
      right = mid;
    } else {
      left = mid + 1;
    }
  }
  return left;
}

```

### CPP

```cpp
class Solution {
public:
  int minAbsoluteSumDiff(vector<int> &nums1, vector<int> &nums2) {
    const int mod = 1e9 + 7;
    vector<int> nums(nums1);
    sort(nums.begin(), nums.end());
    int s = 0, n = nums.size();
    for (int i = 0; i < n; ++i) {
      s = (s + abs(nums1[i] - nums2[i])) % mod;
    }
    int mx = 0;
    for (int i = 0; i < n; ++i) {
      int d1 = abs(nums1[i] - nums2[i]);
      int d2 = 1 << 30;
      int j = lower_bound(nums.begin(), nums.end(), nums2[i]) - nums.begin();
      if (j < n) {
        d2 = min(d2, abs(nums[j] - nums2[i]));
      }
      if (j) {
        d2 = min(d2, abs(nums[j - 1] - nums2[i]));
      }
      mx = max(mx, d1 - d2);
    }
    return (s - mx + mod) % mod;
  }
};

```

### Python

```python
class Solution:
    def minAbsoluteSumDiff(self, nums1: List[int], nums2: List[int]) -> int: mod = 10 ** 9 + 7 nums = sorted(nums1) s = sum(abs(a - b) for a, b in zip(nums1, nums2)) % mod mx = 0 for a, b in zip(nums1, nums2): d1, d2 = abs(a - b), inf i = bisect_left(nums, b) if i < len(nums): d2 = min(d2, abs(nums[i] - b)) if i: d2 = min(d2, abs(nums[i - 1] - b)) mx = max(mx, d1 - d2) return (s - mx + mod) % mod

```