Minimum Absolute Sum Difference LeetCode solution in C++

1
class Solution {
2
 public:
3
  int minAbsoluteSumDiff(vector<int> &nums1, vector<int> &nums2) {
4
    int n = nums1.size();
5
    int M = 1e9 + 7;
6
    int sum = 0;
7
    vector<int> diff(n);
8
    for (int i = 0; i < n; i++) {
9
      diff[i] = abs(nums1[i] - nums2[i]);
10
      // Avoid Integer Overflow Condition
11
      sum = (sum + diff[i]) % M;
12
    }
13
    sort(nums1.begin(), nums1.end());
14
    vector<int> arr(n);
15
    for (int i = 0; i < n; i++) {
16
      int j = lower_bound(nums1.begin(), nums1.end(), nums2[i]) - nums1.begin();
17
      if (j != 0 && j != n)
18
        arr[i] = min(abs(nums2[i] - nums1[j]), abs(nums2[i] - nums1[j - 1]));
19
      else if (j == 0)
20
        arr[i] = abs(nums2[i] - nums1[j]);
21
      else if (j == n)
22
        arr[i] = abs(nums2[i] - nums1[j - 1]);
23
    }
24
    int bestSave = 0;
25
    for (int i = 0; i < n; i++) {
26
      bestSave = max(bestSave, diff[i] - arr[i]);
27
    }
28
    return (M + sum - bestSave) % M;
29
  }
30
};