1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

class Solution {
    public int minAbsoluteSumDiff(int[] nums1, int[] nums2) {
        final int MOD = 1000000007;
        int n = nums1.length;
        int[] rec = new int[n];
        System.arraycopy(nums1, 0, rec, 0, n);
        Arrays.sort(rec);
        int sum = 0, maxGap = 0;
        for (int i = 0; i < n; i++) {
            int gap = Math.abs(nums1[i] - nums2[i]);
            sum = (gap + sum) % MOD;
            int nearOne = getHigherPos(rec, nums2[i]);
            if (nearOne < n) {
                maxGap = Math.max(maxGap, gap - (rec[nearOne] - nums2[i]));
            }
            if (nearOne > 0) {
                maxGap = Math.max(maxGap, gap - (nums2[i] - rec[nearOne - 1]));
            }
        }
        return (sum - maxGap + MOD) % MOD;
    }

    
    private int getHigherPos(int[] arr, int target) {
        int low = 0, high = arr.length - 1;
        if (arr[high] < target) {
            return high + 1;
        } else {
            while (low < high) {
                int mid = (high - low) / 2 + low;
                if (arr[mid] > target) {
                    high = mid;
                } else {
                    low = mid + 1;
                }
            }
        }
        return low;
    } 
}