2163

2163. Minimum Difference in Sums After Removal of Elements (Hard)

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.

 

Example 1:

Input: nums = [3,1,2]
Output: -1
Explanation: Here, nums has 3 elements, so n = 1. 
Thus we have to remove 1 element from nums and divide the array into two equal parts.
- If we remove nums[0] = 3, the array will be [1,2]. The difference in sums of the two parts will be 1 - 2 = -1.
- If we remove nums[1] = 1, the array will be [3,2]. The difference in sums of the two parts will be 3 - 2 = 1.
- If we remove nums[2] = 2, the array will be [3,1]. The difference in sums of the two parts will be 3 - 1 = 2.
The minimum difference between sums of the two parts is min(-1,1,2) = -1. 

Example 2:

Input: nums = [7,9,5,8,1,3]
Output: 1
Explanation: Here n = 2. So we must remove 2 elements and divide the remaining array into two parts containing two elements each.
If we remove nums[2] = 5 and nums[3] = 8, the resultant array will be [7,9,1,3]. The difference in sums will be (7+9) - (1+3) = 12.
To obtain the minimum difference, we should remove nums[1] = 9 and nums[4] = 1. The resultant array becomes [7,5,8,3]. The difference in sums of the two parts is (7+5) - (8+3) = 1.
It can be shown that it is not possible to obtain a difference smaller than 1.

 

Constraints:

• nums.length == 3 * n
• 1 <= n <= 105
• 1 <= nums[i] <= 105

Similar Questions:

• Product of Array Except Self (Medium)
• Find Subsequence of Length K With the Largest Sum (Easy)

Solution 1. Heap

Since we are looking for the minimum difference, we want to minimize the sum of the first part and maximize the sum of the right part.

For the first part, we can use a Max Heap of size N to store the smallest N digits in it.

We traverse from left to right. For each A[i], we push it into the heap. If the heap size is greater than N, we pop the heap top. In this way, we track the smallest N digits and their sum.

Similarly for the right part, but we want the greatest N digits.

// OJ: https://leetcode.com/problems/minimum-difference-in-sums-after-removal-of-elements/
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(N)
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;
    }
};

Discuss

https://leetcode.com/problems/minimum-difference-in-sums-after-removal-of-elements/discuss/1746989/