2163. Minimum Difference in Sums After Removal of Elements

You are given a 0-indexed integer array nums consisting of 3 * n elements.

You are allowed to remove any subsequence of elements of size exactly n from nums. The remaining 2 * n elements will be divided into two equal parts:

• The first n elements belonging to the first part and their sum is sumfirst.
• The next n elements belonging to the second part and their sum is sumsecond.

The difference in sums of the two parts is denoted as sumfirst - sumsecond.

• For example, if sumfirst = 3 and sumsecond = 2, their difference is 1.
• Similarly, if sumfirst = 2 and sumsecond = 3, their difference is -1.

Return the minimum difference possible between the sums of the two parts after the removal of n elements.

• Time : O(nlogn)
• Space : O(n)

class Solution {
    long long dp[100001];
public:
    long long minimumDifference(vector<int>& nums) {
        long long n = nums.size()/3, lsum = 0, rsum = 0, res;
        priority_queue<int> lq;
        priority_queue<int, vector<int>, greater<int>> rq;
        for(int i = 0; i < n; i++) {
            lsum += nums[i];
            lq.push(nums[i]);
        }
        for(int i = 2*n; i < 3*n; i++) {
            rsum += nums[i];
            rq.push(nums[i]);
        }
        dp[0]= lsum;
        for(int i = n; i < 2*n; i++) {
            if(lq.top() > nums[i]) {
                lsum = lsum + nums[i] - lq.top();
                lq.pop();
                lq.push(nums[i]);
            }
            dp[i - n + 1] = lsum;
        }
        res = dp[n]-rsum;
        for(int i = 2*n-1; i >= n; i--) {
            if(rq.top() < nums[i]) {
                rsum = rsum + nums[i] - rq.top();
                rq.pop();
                rq.push(nums[i]);
            }
            res = min(res, dp[i-n] - rsum);
        }

        return res;
    }
};