Description

Submission

class Solution {
    const int M = 1e9 + 7;
public:
    int minAbsoluteSumDiff(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        vector<int> nums = nums1; 
        sort(nums.begin(), nums.end());

        int original = 0;
        int maxDiff = 0;
        for(int i = 0; i < n; ++i) {
            int curDiff = INT_MAX;
            auto it = upper_bound(nums.begin(), nums.end(), nums2[i]);
            if(it != nums.end()) {
                curDiff = min(curDiff, abs(*it - nums2[i]));
            }

            if(it != nums.begin()) {
                curDiff = min(curDiff, abs(*(it-1) - nums2[i]));
            }

            maxDiff = max(maxDiff, abs(nums1[i] - nums2[i]) - curDiff);
            original = (original + abs(nums1[i] - nums2[i])) % M;
        }

        return (original + M - maxDiff) % M;
    }
};