Minimum absolute sum difference

Array Binary Search Sorting Ordered Set

32.2% acceptance

Feb 25, 2026

1097

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 10^9 + 7. |x| is defined as x if x >= 0, or -x if x < 0.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn min_absolute_sum_diff(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let n = nums1.len();
    let mut sorted = nums1.clone();
    sorted.sort_unstable();

    let mut total: i64 = 0;
    let mut max_save: i64 = 0;

    for i in 0..n {
      let diff = (nums1[i] - nums2[i]).abs() as i64;
      total += diff;
      // Binary search for best replacement value close to nums2[i]
      let target = nums2[i];
      let pos = sorted.partition_point(|&x| x < target);
      // Check pos and pos-1
      if pos < sorted.len() {
        let new_diff = (sorted[pos] - target).abs() as i64;
        max_save = max_save.max(diff - new_diff);
      }
      if pos > 0 {
        let new_diff = (sorted[pos - 1] - target).abs() as i64;
        max_save = max_save.max(diff - new_diff);
      }
    }
    ((total - max_save) % MOD) as i32
  }
}