Minimum Difference in Sums After Removal of Elements LeetCode solution in Java

1
class Solution {
2
  public long minimumDifference(int[] nums) {
3
    int n = nums.length; // length of nums
4
    int len3 = n / 3; // 1/3 length
5
    long res = Long.MAX_VALUE; // final result;
6
    // Try to make first part as min as possible;
7
    // first[m] store the value, the min value of the size=len3, from[0,1,..., m];
8
    long[] first = new long[n];
9
    // Try to make second part as max as possible;
10
    // second[m] store the value, the max value of the size=len3, from[m,...,n-1];
11
    long[] second = new long[n];
12

13
    // --------------------for first part compute -------------------------------------
14
    // Build max heap for first part;
15
    PriorityQueue<Integer> max = new PriorityQueue<Integer>(Comparator.reverseOrder());
16

17
    long sum = 0;
18

19
    // Initialize with the first 1/3 n part.
20
    for (int i = 0; i < len3; i++) {
21
      sum += nums[i];
22
      max.add(nums[i]);
23
    }
24
    // For the second part between 1/3 ~ 2/3. When we move to next index.
25
    // we keep the sum as total 1/3n size: each time poll the max one and add the new one;
26
    // And we keep tracking the exchange by long[] first;
27
    //
28
    for (int i = len3; i <= 2 * len3; i++) {
29
      first[i] = sum; // add sum from 1/3
30
      max.add(nums[i]); // put new one in queue;
31
      sum += nums[i]; // sum + new one;
32
      sum -= max.poll(); // sum - max one;
33
    }
34
    // --------------------for second part compute -----------------------
35
    sum = 0;
36
    // Build min heap for first part;
37
    PriorityQueue<Integer> min = new PriorityQueue<Integer>();
38
    // Initialize with the last 1/3 n part.
39
    for (int i = 0; i < len3; i++) {
40
      sum += nums[n - 1 - i];
41
      min.add(nums[n - 1 - i]);
42
    }
43
    // For the second part between 2/3~1/3 When we move to next index:
44
    // we keep update the sum with(+ new element, - min element), and update second;
45
    for (int i = len3; i <= 2 * len3; i++) {
46
      second[n - i] = sum;
47
      min.add(nums[n - 1 - i]);
48
      sum += nums[n - 1 - i];
49
      sum -= min.poll();
50
    }
51
    // -----------------compute the final result------------
52

53
    // find the max value in second part [ i,..., n-1];
54
    // find the min value in first part [0,....,i];
55
    // find the result;
56
    for (int i = len3; i <= 2 * len3; i++) {
57
      res = Math.min(res, first[i] - second[i]);
58
    }
59

60
    return res;
61
  }
62
}