## 1818. Minimum Absolute Sum Difference

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:

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

## Rust Solution

``````struct Solution;

use std::collections::BTreeSet;
use std::iter::FromIterator;

const MOD: i64 = 1_000_000_007;

impl Solution {
fn min_absolute_sum_diff(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
let bts: BTreeSet<i32> = BTreeSet::from_iter(nums1.clone());
let n = nums1.len();
let mut max = 0;
let mut sum: i64 = 0;
for i in 0..n {
let x = nums2[i];
let y = nums1[i];
let z = (x - y).abs();
sum += z as i64;
if let Some(left) = bts.range(..=x).next_back() {
if (x - left) < z {
max = max.max(z - (x - left));
}
}
if let Some(right) = bts.range(x..).next() {
if (right - x) < z {
max = max.max(z - (right - x));
}
}
}
((sum - max as i64) % MOD) as i32
}
}

#[test]
fn test() {
let nums1 = vec![1, 7, 5];
let nums2 = vec![2, 3, 5];
let res = 3;
assert_eq!(Solution::min_absolute_sum_diff(nums1, nums2), res);
let nums1 = vec![2, 4, 6, 8, 10];
let nums2 = vec![2, 4, 6, 8, 10];
let res = 0;
assert_eq!(Solution::min_absolute_sum_diff(nums1, nums2), res);
let nums1 = vec![1, 10, 4, 4, 2, 7];
let nums2 = vec![9, 3, 5, 1, 7, 4];
let res = 20;
assert_eq!(Solution::min_absolute_sum_diff(nums1, nums2), res);
}
``````

Having problems with this solution? Click here to submit an issue on github.