2163. Minimum Difference in Sums After Removal of Elements

 JAVA

• class Solution {
      public long minimumDifference(int[] nums) {
          int m = nums.length;
          int n = m / 3;
          long s = 0;
          long[] pre = new long[m + 1];
          PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
          for (int i = 1; i <= n * 2; ++i) {
              int x = nums[i - 1];
              s += x;
              pq.offer(x);
              if (pq.size() > n) {
                  s -= pq.poll();
              }
              pre[i] = s;
          }
          s = 0;
          long[] suf = new long[m + 1];
          pq = new PriorityQueue<>();
          for (int i = m; i > n; --i) {
              int x = nums[i - 1];
              s += x;
              pq.offer(x);
              if (pq.size() > n) {
                  s -= pq.poll();
              }
              suf[i] = s;
          }
          long ans = 1L << 60;
          for (int i = n; i <= n * 2; ++i) {
              ans = Math.min(ans, pre[i] - suf[i + 1]);
          }
          return ans;
      }
  }

C++

class Solution {
public:
    long long minimumDifference(vector<int>& A) {
        priority_queue<int> L; // storing the smallest N digits in the first part
        priority_queue<int,vector<int>, greater<>> R; // storing the greatest N digits in the right part
        long N = A.size() / 3, ans = LLONG_MAX;
        vector<long> right(A.size());
        for (long i = A.size() - 1, sum = 0; i >= N; --i) { // calculate the greatest N digits in the right part
            R.push(A[i]);
            sum += A[i];
            if (R.size() > N) {
                sum -= R.top();
                R.pop();
            }
            if (R.size() == N) right[i] = sum; // `right[i]` is the maximum sum of `N` digits in `A[i:]`
        }
        for (long i = 0, left = 0; i < A.size() - N; ++i) {
            L.push(A[i]);
            left += A[i];
            if (L.size() > N) {
                left -= L.top();
                L.pop();
            }
            if (L.size() == N) ans = min(ans, left - right[i + 1]);
        }
        return ans;
    }
};