Minimum Difference in Sums After Removal of Elements
HardUpdated: Aug 2, 2025
Practice on:
Problem
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
nelements belonging to the first part and their sum issumfirst. - The next
nelements belonging to the second part and their sum issumsecond.
The difference in sums of the two parts is denoted as sumfirst -sumsecond.
- For example, if
sumfirst = 3andsumsecond = 2, their difference is1. - Similarly, if
sumfirst = 2andsumsecond = 3, their difference is-1.
Return _theminimum difference possible between the sums of the two parts after the removal of _n elements.
Examples
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 * n1 <= n <= 10^51 <= nums[i] <= 10^5
Solution
Method 1 – Heap Optimization for Prefix and Suffix Sums
Intuition
To minimize the difference, we want the largest possible sum for the first part and the smallest possible sum for the second part after removing n elements. We use heaps to efficiently track the best n elements to remove from each side.
Approach
- Let n = nums.length / 3.
- For the first 2n elements, use a max-heap to keep the smallest n elements (for prefix sum).
- For the last 2n elements, use a min-heap to keep the largest n elements (for suffix sum).
- For each split point, calculate the difference between the prefix and suffix sums.
- Return the minimum difference found.
Code
C++
class Solution {
public:
long long minimumDifference(vector<int>& nums) {
int n = nums.size() / 3;
priority_queue<int> maxh;
vector<long long> left(n * 2 + 1);
long long sum = 0;
for (int i = 0; i < n * 2; ++i) {
sum += nums[i];
maxh.push(nums[i]);
if (maxh.size() > n) {
sum -= maxh.top();
maxh.pop();
}
left[i + 1] = sum;
}
priority_queue<int, vector<int>, greater<int>> minh;
vector<long long> right(n * 2 + 1);
sum = 0;
for (int i = nums.size() - 1; i >= n; --i) {
sum += nums[i];
minh.push(nums[i]);
if (minh.size() > n) {
sum -= minh.top();
minh.pop();
}
right[i - n] = sum;
}
long long ans = LLONG_MAX;
for (int i = n; i <= n * 2; ++i) {
ans = min(ans, left[i] - right[i]);
}
return ans;
}
};
Go
// Skipped for brevity due to heap implementation complexity in Go.
Java
class Solution {
public long minimumDifference(int[] nums) {
int n = nums.length / 3;
PriorityQueue<Long> maxh = new PriorityQueue<>(Collections.reverseOrder());
PriorityQueue<Long> minh = new PriorityQueue<>();
List<Long> left = new ArrayList<>();
List<Long> right = new ArrayList<>();
long sum = 0;
for (int i = 0; i < n; i++) {
maxh.add((long)nums[i]);
sum += nums[i];
}
left.add(sum);
for (int i = n; i < 2 * n; i++) {
maxh.add((long)nums[i]);
sum += nums[i];
sum -= maxh.poll();
left.add(sum);
}
sum = 0;
for (int i = 3 * n - 1; i >= 2 * n; i--) {
minh.add((long)nums[i]);
sum += nums[i];
}
right.add(sum);
for (int i = 2 * n - 1; i >= n; i--) {
minh.add((long)nums[i]);
sum += nums[i];
sum -= minh.poll();
right.add(sum);
}
Collections.reverse(right);
long ans = Long.MAX_VALUE;
for (int i = 0; i < left.size(); i++) {
ans = Math.min(ans, left.get(i) - right.get(i));
}
return ans;
}
}
Kotlin
class Solution {
fun minimumDifference(nums: IntArray): Long {
val n = nums.size / 3
val maxh = PriorityQueue<Int>(compareByDescending { it })
val left = LongArray(n * 2 + 1)
var sum = 0L
for (i in 0 until n * 2) {
sum += nums[i]
maxh.add(nums[i])
if (maxh.size > n) {
sum -= maxh.poll()
}
left[i + 1] = sum
}
val minh = PriorityQueue<Int>()
val right = LongArray(n * 2 + 1)
sum = 0L
for (i in nums.size - 1 downTo n) {
sum += nums[i]
minh.add(nums[i])
if (minh.size > n) {
sum -= minh.poll()
}
right[i - n] = sum
}
var ans = Long.MAX_VALUE
for (i in n..n * 2) {
ans = minOf(ans, left[i] - right[i])
}
return ans
}
}
Python
def minimum_difference(nums: list[int]) -> int:
import heapq
n = len(nums) // 3
maxh, minh = [], []
left = [0] * (2 * n + 1)
s = 0
for i in range(2 * n):
s += nums[i]
heapq.heappush(maxh, -nums[i])
if len(maxh) > n:
s += heapq.heappop(maxh)
left[i + 1] = s
right = [0] * (2 * n + 1)
s = 0
for i in range(len(nums) - 1, n - 1, -1):
s += nums[i]
heapq.heappush(minh, nums[i])
if len(minh) > n:
s -= heapq.heappop(minh)
right[i - n] = s
ans = float('inf')
for i in range(n, 2 * n + 1):
ans = min(ans, left[i] - right[i])
return ans
Rust
// Skipped for brevity due to heap implementation complexity in Rust.
TypeScript
// Skipped for brevity due to heap implementation complexity in TypeScript.
Complexity
- ⏰ Time complexity:
O(n log n), for maintaining heaps and traversing the array. - 🧺 Space complexity:
O(n), for prefix/suffix arrays and heaps.