Minimum Absolute Sum Difference LeetCode solution in Java

1
class Solution {
2
  public int minAbsoluteSumDiff(int[] nums1, int[] nums2) {
3
    int mod = (int) 1e9 + 7;
4

5
    // Sorted copy of nums1 to use for binary search
6
    int[] snums1 = nums1.clone();
7
    Arrays.sort(snums1);
8

9
    int maxDiff = 0; // maximum difference between original and new absolute diff
10
    int pos = 0; // where the maximum difference occurs
11
    int newn1 = 0; // nums1 value to copy to nums1[pos]
12

13
    // For each array position i from 0 to n-1, find up to two elements
14
    // in nums1 that are closest to nums2[i] (one on each side of nums2[i]).
15
    // Calculate a new absolute difference for each of these elements.
16
    for (int i = 0; i < nums2.length; i++) {
17
      int n2 = nums2[i];
18
      int origDiff = Math.abs(nums1[i] - n2);
19

20
      // Find the largest element in nums1 that is less than or equal to
21
      // the current element in nums2, if such an element exists.
22
      int floor = arrayFloor(snums1, n2);
23
      if (floor > Integer.MIN_VALUE) {
24
        // If a valid element exists, calculate a new absolute difference
25
        // at the current position, and calculate how much smaller this is
26
        // than the current absolute difference. If the result is better
27
        // than what we have seen so far, update the maximum difference and
28
        // save the data for the current position.
29
        int newDiff = Math.abs(floor - n2);
30
        int diff = origDiff - newDiff;
31
        if (diff > maxDiff) {
32
          pos = i;
33
          newn1 = floor;
34
          maxDiff = diff;
35
        }
36
      }
37

38
      // Find the smallest element in nums1 that is greater than or equal to
39
      // the current element in nums2, if such an element exists.
40
      int ceiling = arrayCeiling(snums1, n2);
41
      if (ceiling < Integer.MAX_VALUE) {
42
        // Same as above
43
        int newDiff = Math.abs(ceiling - n2);
44
        int diff = origDiff - newDiff;
45
        if (diff > maxDiff) {
46
          pos = i;
47
          newn1 = ceiling;
48
          maxDiff = diff;
49
        }
50
      }
51
    }
52

53
    // If we found a replacement value, overwrite the original value.
54
    if (newn1 > 0) {
55
      nums1[pos] = newn1;
56
    }
57

58
    // Calculate the absolute sum difference with the replaced value.
59
    int sum = 0;
60
    for (int i = 0; i < nums1.length; i++) {
61
      sum = (sum + Math.abs(nums1[i] - nums2[i])) % mod;
62
    }
63

64
    return sum;
65
  }
66

67
  //
68
  // Array versions of TreeSet.floor and TreeSet.ceiling
69
  //
70

71
  // Greatest element less than or equal to val
72
  private int arrayFloor(int[] arr, int val) {
73
    int lo = 0;
74
    int hi = arr.length - 1;
75
    int max = Integer.MIN_VALUE;
76

77
    while (lo <= hi) {
78
      int mid = lo + (hi - lo) / 2;
79
      if (arr[mid] <= val) {
80
        max = arr[mid];
81
        lo = mid + 1;
82
      } else {
83
        hi = mid - 1;
84
      }
85
    }
86

87
    return max;
88
  }
89

90
  // Smallest element greater than or equal to val
91
  private int arrayCeiling(int[] arr, int val) {
92
    int lo = 0;
93
    int hi = arr.length - 1;
94
    int min = Integer.MAX_VALUE;
95

96
    while (lo <= hi) {
97
      int mid = lo + (hi - lo) / 2;
98
      if (arr[mid] >= val) {
99
        min = arr[mid];
100
        hi = mid - 1;
101
      } else {
102
        lo = mid + 1;
103
      }
104
    }
105

106
    return min;
107
  }
108
}