Minimum Difference in Sums After Removal of Elements Solution
Minimum Difference in Sums After Removal of Elements solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Minimum Difference in Sums After Removal of Elements is a hard coding problem on arrays, dynamic programming and heap, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Arrays, Dynamic Programming, Heap
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an array nums of 3 * n elements.
Remove any n of them (they need not be contiguous). The 2 * n elements that remain keep their order and are split in two: the first n form the first part, with sum sumfirst, and the last n form the second part, with sum sumsecond.
The difference of the split is sumfirst - sumsecond. Return the minimum difference you can achieve.
Constraint note: values are capped at 10^4 (the original allows 10^5) so every sum fits in a 32-bit integer.
Example 1
Input: nums = [4,1,6,2,8,3]
Output: -9
Explanation: Remove 2 and 3: the remaining [4,1,6,8] splits into [4,1] (sum 5) and [6,8] (sum 14).
Example 2
Input: nums = [3,1,2]
Output: -1
Explanation: Remove 3: the parts are [1] and [2].
Example 3
Input: nums = [7,9,5,8,1,3]
Output: 1
Constraints
nums.length == 3 * n1 <= n <= 10^51 <= nums[i] <= 10^4
Hints for Minimum Difference in Sums After Removal of Elements
Hint 1
After the removal there is a cut position
kwithn <= k <= 2n: the first part comes fromnums[0..k)and the second fromnums[k..3n).Hint 2
For a fixed cut, the first part should be the
nsmallest values of the prefix and the second part thenlargest of the suffix.Hint 3
Compute the best prefix sum for every cut with a max-heap of size
n(evict the largest), and the best suffix sum with a min-heap of sizenscanning from the right.
How to solve Minimum Difference in Sums After Removal of Elements
Fix the boundary k between the two parts. Then the parts are independent: minimise the first by keeping the n smallest of nums[0..k), maximise the second by keeping the n largest of nums[k..3n). Both families of answers come from one sweep each with a bounded heap.
Approach
- Left sweep: start with the first
nvalues in a max-heap and their sum asleft[n]. Fori = n .. 2n-1, pushnums[i], pop the largest and update the sum; recordleft[i+1]. - Right sweep: start with the last
nvalues in a min-heap and their sum asright[2n]. Fori = 2n-1 down to n, pushnums[i], pop the smallest and update the sum; recordright[i]. - Return the minimum of
left[k] - right[k]overk = n .. 2n.
Why it works
Any valid removal leaves a first part entirely before a second part, so some k in [n, 2n] separates them, and for that k the choice inside each side is unconstrained — the extremal n values are optimal. The bounded heaps maintain exactly those extremal sets as the boundary moves one step at a time.
Complexity
- Time —
O(n log n) - Space —
O(n)
Pitfalls
- The cut ranges over
n + 1positions, both ends included. - The left side needs the
nsmallest (evict the maximum), the right side thenlargest (evict the minimum) — swapping them maximises the difference instead. - With the original limits the sums exceed 32 bits; accumulate in 64-bit where the language needs it.
Reference solution
Python
from typing import List
import heapq
def minimumDifference(nums: List[int]) -> int:
n = len(nums) // 3
# left[i]: least sum of n values among nums[:n + i]
heap = [-v for v in nums[:n]]
heapq.heapify(heap)
s = sum(nums[:n])
left = [s]
for i in range(n, 2 * n):
s += nums[i]
heapq.heappush(heap, -nums[i])
s += heapq.heappop(heap) # evict the largest
left.append(s)
# sweep the cut from 2n down to n with the n largest values of the suffix
heap = nums[2 * n:]
heapq.heapify(heap)
s = sum(heap)
best = left[n] - s
for i in range(2 * n - 1, n - 1, -1):
s += nums[i]
heapq.heappush(heap, nums[i])
s -= heapq.heappop(heap) # evict the smallest
best = min(best, left[i - n] - s)
return bestJava
public static int minimumDifference(int[] nums) {
int n = nums.length / 3;
long[] left = new long[n + 1];
PriorityQueue<Integer> low = new PriorityQueue<>(Collections.reverseOrder());
long sum = 0;
for (int i = 0; i < n; i++) {
low.add(nums[i]);
sum += nums[i];
}
left[0] = sum;
for (int i = n; i < 2 * n; i++) {
low.add(nums[i]);
sum += nums[i] - low.poll(); // evict the largest
left[i - n + 1] = sum;
}
PriorityQueue<Integer> high = new PriorityQueue<>();
sum = 0;
for (int i = 2 * n; i < 3 * n; i++) {
high.add(nums[i]);
sum += nums[i];
}
long best = left[n] - sum;
for (int i = 2 * n - 1; i >= n; i--) {
high.add(nums[i]);
sum += nums[i] - high.poll(); // evict the smallest
best = Math.min(best, left[i - n] - sum);
}
return (int) best;
}C++
int minimumDifference(vector<int>& nums) {
int n = nums.size() / 3;
vector<long long> left(n + 1);
priority_queue<int> low;
long long sum = 0;
for (int i = 0; i < n; i++) {
low.push(nums[i]);
sum += nums[i];
}
left[0] = sum;
for (int i = n; i < 2 * n; i++) {
low.push(nums[i]);
sum += nums[i] - low.top(); // evict the largest
low.pop();
left[i - n + 1] = sum;
}
priority_queue<int, vector<int>, greater<int>> high;
sum = 0;
for (int i = 2 * n; i < 3 * n; i++) {
high.push(nums[i]);
sum += nums[i];
}
long long best = left[n] - sum;
for (int i = 2 * n - 1; i >= n; i--) {
high.push(nums[i]);
sum += nums[i] - high.top(); // evict the smallest
high.pop();
best = min(best, left[i - n] - sum);
}
return (int) best;
}JavaScript
var minimumDifference = function(nums) {
var n = nums.length / 3;
// left[i]: least sum of n values among the first n + i (max-heap via negation)
var low = [];
var sum = 0;
for (var i = 0; i < n; i++) {
heapPush(low, -nums[i]);
sum += nums[i];
}
var left = [sum];
for (var i2 = n; i2 < 2 * n; i2++) {
heapPush(low, -nums[i2]);
sum += nums[i2] + heapPop(low); // evict the largest
left.push(sum);
}
// the n largest of the suffix, cut moving from 2 * n down to n
var high = [];
sum = 0;
for (var j = 2 * n; j < 3 * n; j++) {
heapPush(high, nums[j]);
sum += nums[j];
}
var best = left[n] - sum;
for (var k = 2 * n - 1; k >= n; k--) {
heapPush(high, nums[k]);
sum += nums[k] - heapPop(high); // evict the smallest
best = Math.min(best, left[k - n] - sum);
}
return best;
};
var heapPush = function(h, v) {
h.push(v);
var i = h.length - 1;
while (i > 0) {
var p = (i - 1) >> 1;
if (h[p] <= h[i]) break;
var t = h[p]; h[p] = h[i]; h[i] = t;
i = p;
}
};
var heapPop = function(h) {
var top = h[0];
var last = h.pop();
if (h.length > 0) {
h[0] = last;
var j = 0;
for (;;) {
var l = 2 * j + 1, r = l + 1, s = j;
if (l < h.length && h[l] < h[s]) s = l;
if (r < h.length && h[r] < h[s]) s = r;
if (s === j) break;
var t = h[s]; h[s] = h[j]; h[j] = t;
j = s;
}
}
return top;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming