2163. Minimum Difference in Sums After Removal of Elements LeetCode Solution
In this guide, you will get 2163. Minimum Difference in Sums After Removal of Elements LeetCode Solution with the best time and space complexity. The solution to Minimum Difference in Sums After Removal of Elements problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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.
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.
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
Complexity Analysis
Time Complexity: O(n\log n)
Space Complexity: O(n)
2163. Minimum Difference in Sums After Removal of Elements LeetCode Solution in C++
class Solution {
public:
long long minimumDifference(vector<int>& nums) {
const int n = nums.size() / 3;
long ans = LONG_MAX;
long leftSum = 0;
long rightSum = 0;
// The left part should be as small as possible.
priority_queue<int> maxHeap;
// The right part should be as big as possible.
priority_queue<int, vector<int>, greater<>> minHeap;
// minLeftSum[i] := the minimum of the sum of n nums in nums[0..i)
vector<long> minLeftSum(nums.size());
for (int i = 0; i < 2 * n; ++i) {
maxHeap.push(nums[i]);
leftSum += nums[i];
if (maxHeap.size() == n + 1)
leftSum -= maxHeap.top(), maxHeap.pop();
if (maxHeap.size() == n)
minLeftSum[i] = leftSum;
}
for (int i = nums.size() - 1; i >= n; --i) {
minHeap.push(nums[i]);
rightSum += nums[i];
if (minHeap.size() == n + 1)
rightSum -= minHeap.top(), minHeap.pop();
if (minHeap.size() == n)
ans = min(ans, minLeftSum[i - 1] - rightSum);
}
return ans;
}
}; /* code provided by PROGIEZ */
2163. Minimum Difference in Sums After Removal of Elements LeetCode Solution in Java
class Solution {
public long minimumDifference(int[] nums) {
final int n = nums.length / 3;
long ans = Long.MAX_VALUE;
long leftSum = 0;
long rightSum = 0;
// The left part should be as small as possible.
Queue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
// The right part should be as big as possible.
Queue<Integer> minHeap = new PriorityQueue<>();
// minLeftSum[i] := the minimum of the sum of n nums in nums[0..i)
long[] minLeftSum = new long[nums.length];
for (int i = 0; i < 2 * n; ++i) {
maxHeap.offer(nums[i]);
leftSum += nums[i];
if (maxHeap.size() == n + 1)
leftSum -= maxHeap.poll();
if (maxHeap.size() == n)
minLeftSum[i] = leftSum;
}
for (int i = nums.length - 1; i >= n; --i) {
minHeap.offer(nums[i]);
rightSum += nums[i];
if (minHeap.size() == n + 1)
rightSum -= minHeap.poll();
if (minHeap.size() == n)
ans = Math.min(ans, minLeftSum[i - 1] - rightSum);
}
return ans;
}
} // code provided by PROGIEZ
2163. Minimum Difference in Sums After Removal of Elements LeetCode Solution in Python
class Solution:
def minimumDifference(self, nums: list[int]) -> int:
n = len(nums) // 3
ans = math.inf
leftSum = 0
rightSum = 0
maxHeap = [] # Left part, as small as possible
minHeap = [] # Right part, as big as possible
# minLeftSum[i] := the minimum of the sum of n nums in nums[0..i)
minLeftSum = [0] * len(nums)
for i in range(2 * n):
heapq.heappush(maxHeap, -nums[i])
leftSum += nums[i]
if len(maxHeap) == n + 1:
leftSum += heapq.heappop(maxHeap)
if len(maxHeap) == n:
minLeftSum[i] = leftSum
for i in range(len(nums) - 1, n - 1, -1):
heapq.heappush(minHeap, nums[i])
rightSum += nums[i]
if len(minHeap) == n + 1:
rightSum -= heapq.heappop(minHeap)
if len(minHeap) == n:
ans = min(ans, minLeftSum[i - 1] - rightSum)
return ans # code by PROGIEZ
