Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2163.html
2163. Minimum Difference in Sums After Removal of Elements (Hard)
You are given a 0indexed 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 issum_{first}
.  The next
n
elements belonging to the second part and their sum issum_{second}
.
The difference in sums of the two parts is denoted as sum_{first}  sum_{second}
.
 For example, if
sum_{first} = 3
andsum_{second} = 2
, their difference is1
.  Similarly, if
sum_{first} = 2
andsum_{second} = 3
, their difference is1
.
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 <= 10^{5}
1 <= nums[i] <= 10^{5}
Similar Questions:
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/minimumdifferenceinsumsafterremovalofelements/ // 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; } };

// Todo

# 2163. Minimum Difference in Sums After Removal of Elements # https://leetcode.com/problems/minimumdifferenceinsumsafterremovalofelements/ from sortedcontainers import SortedList class Solution: def minimumDifference(self, nums: List[int]) > int: m = len(nums) n = m // 3 left = SortedList(nums[:n]) right = SortedList(nums[n:]) sumLeft = sum(left) sumRight = sum(right[n:]) res = sumLeft  sumRight for i in range(n, 2 * n): index = right.bisect_left(nums[i]) if index >= len(right)  n: sumRight = nums[i] sumRight += right[n1] index = left.bisect_left(nums[i]) if index < n: sumLeft += nums[i] sumLeft = left[n  1] right.discard(nums[i]) left.add(nums[i]) res = min(res, sumLeft  sumRight) return res
Discuss
https://leetcode.com/problems/minimumdifferenceinsumsafterremovalofelements/discuss/1746989/