Skip to content

1818. Minimum Absolute Sum Difference 👍

  • Time: $O(n\log n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
 public:
  int minAbsoluteSumDiff(vector<int>& nums1, vector<int>& nums2) {
    constexpr int kMod = 1'000'000'007;
    long sumDiff = 0;
    long maxDecrement = 0;
    set<int> sorted(nums1.begin(), nums1.end());

    for (int i = 0; i < nums1.size(); ++i) {
      const long currDiff = abs(nums1[i] - nums2[i]);
      sumDiff += currDiff;
      const auto it = sorted.lower_bound(nums2[i]);
      if (it != sorted.begin())
        maxDecrement = max(maxDecrement, currDiff - abs(*prev(it) - nums2[i]));
      if (it != sorted.end())
        maxDecrement = max(maxDecrement, currDiff - abs(*it - nums2[i]));
    }

    return (sumDiff - maxDecrement) % kMod;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
  public int minAbsoluteSumDiff(int[] nums1, int[] nums2) {
    final int kMod = 1_000_000_007;
    long sumDiff = 0;
    long maxDecrement = 0;
    TreeSet<Integer> sorted = new TreeSet<>();

    for (final int num : nums1)
      sorted.add(num);

    for (int i = 0; i < nums1.length; ++i) {
      final long currDiff = (long) Math.abs(nums1[i] - nums2[i]);
      sumDiff += currDiff;
      Integer ceiling = sorted.ceiling(nums2[i]);
      Integer floor = sorted.floor(nums2[i]);
      if (ceiling != null)
        maxDecrement = Math.max(maxDecrement, currDiff - (long) Math.abs(ceiling - nums2[i]));
      if (floor != null)
        maxDecrement = Math.max(maxDecrement, currDiff - (long) Math.abs(floor - nums2[i]));
    }

    return (int) ((sumDiff - maxDecrement) % kMod);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
  def minAbsoluteSumDiff(self, nums1: List[int], nums2: List[int]) -> int:
    ans = math.inf
    diffs = [abs(a - b) for a, b in zip(nums1, nums2)]
    sumDiff = sum(diffs)

    nums1.sort()

    for num, diff in zip(nums2, diffs):
      i = bisect.bisect_left(nums1, num)
      if i > 0:
        ans = min(ans, sumDiff - diff + abs(num - nums1[i - 1]))
      if i < len(nums1):
        ans = min(ans, sumDiff - diff + abs(num - nums1[i]))

    return ans % int(1e9 + 7)