Minimum Difference in Sums After Removal of Elements solution and explanation
Infosys
Google
9 more videos on this problem
Minimum Difference in Sums After Removal of Elements | Detailed Explanation | Leetcode 2163 | MIKcodestorywithMIK · 41:38 · 10K views
Minimum Difference in Sums After Removal of Elements | Leetcode 2163Techdose · 28:22 · 3K views
2163. Minimum Difference in Sums After Removal of Elements || LeetCode 2163 || Biweekly LeetCode 71Bro Coders · 15:57 · 3K views
Minimum Difference in Sums After Removal of Elements | 2163 LeetCode | Leetcode BiWeekly Contest 71CodeWithSunny · 22:56 · 1K views
2163. Minimum Difference in Sums After Removal of Elements | Leetcode Daily - PythonLeetcode Daily · 5:30 · 864 views
Daily Leetcode #1935: Jul 18, 2025 - 2163. Minimum Difference in Sums After Removal of ElementsProgramming Live with Larry · 39:34 · 689 views
2163. Minimum Difference in Sums After Removal of Elements (Leetcode Hard)Programming Live with Larry · 38:47 · 616 views
Minimum Difference in Sums After Removal of Elements | LeetCode 2163 - Pythonimpoldev · 19:17 · 450 views
Leetcode 2163. Minimum Difference in Sums After Removal of Elements | Heaps Prefix Suffix PythonStatLearn Tech · 21:04 · 301 views
Leetcode 2163. Minimum Difference in Sums After Removal of Elements || Prefix Sum || Priority QueueTuan Dino · 23:18 · 65 views
The 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 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 * n1 <= n <= 1051 <= nums[i] <= 105
Approach overview
Problem Overview: You get an array of length 3n. Remove exactly n elements so the remaining 2n elements form two groups of n each (left and right). The goal is to minimize sum(left) - sum(right). The challenge is choosing which n elements to remove so the left side stays as small as possible while the right side becomes as large as possible.
Approach 1: Prefix and Suffix Analysis with Priority Queues (O(n log n) time, O(n) space)
Split the thinking into two independent goals. From the left side, you want the smallest possible sum of n elements among the first 2n positions. From the right side, you want the largest possible sum of n elements among the last 2n positions. Use a max-heap to keep the n smallest elements while scanning left to right. Store the running minimum sums in a prefix array. Then scan right to left using a min-heap to keep the n largest elements and store those sums as suffix values. For every valid split point between the two regions, compute prefix[i] - suffix[i+1] and track the minimum difference. Heap push/pop operations keep the selected set optimal at every step. This approach relies heavily on heap (priority queue) operations and sequential array traversal.
Approach 2: Sliding Window with Unordered Removal (O(n log n) time, O(n) space)
Another way to model the same decision process is maintaining two dynamic windows that track which elements currently belong to the left group and the right group. Balanced containers such as multiset or indexed heaps maintain the chosen n elements while allowing arbitrary removal when the window shifts. As the boundary moves across the middle section of the array, elements can migrate between candidate sets. Each update adjusts the running sum of the selected elements. The structure guarantees that the left container always holds the smallest possible n values and the right container keeps the largest n values. Conceptually this behaves like a sliding optimization layer over the array while maintaining optimal subsets. The reasoning resembles state tracking often seen in dynamic programming, but implemented with ordered structures.
Recommended for interviews: The prefix–suffix heap approach is the expected solution. It clearly separates the two optimization goals and runs in O(n log n) time with simple heap operations. Interviewers usually look for the insight that the first half should minimize its sum while the second half maximizes its sum, and that both can be computed independently using priority queues.
Approach 1: Prefix and Suffix Analysis with Priority Queues
This approach uses a combination of prefix and suffix analysis with the help of priority queues to find the minimum difference between the sums of two parts after removing n elements.
We maintain two arrays for prefix and suffix information: one to track the maximum sum of n elements from the beginning (prefix) and one for the minimum sum of n elements from the end (suffix). By continuously tracking these sums in a priority queue (max-heap for prefix and min-heap for suffix), we iterate to find the minimum difference possible between them.
import heapq
def minimumDifference(nums):
n = len(nums) // 3
prefixSum = [0] * (3 * n + 1)
minHeap = []
suffixSum = sum(nums[2 * n:])
maxHeap = []
result = float('inf')
for i in range(3 * n):
heapq.heappush(minHeap, nums[i])
prefixSum[i + 1] = prefixSum[i] + nums[i]
if len(minHeap) > n:
removed = heapq.heappop(minHeap)
prefixSum[i + 1] -= removed
for i in range(n):
heapq.heappush(maxHeap, -nums[3 * n - 1 - i])
suffixSum -= nums[3 * n - 1 - i]
if len(maxHeap) > n:
removed = -heapq.heappop(maxHeap)
suffixSum += removed
result = min(result, prefixSum[2 * n - i] - suffixSum)
return result
nums = [7,9,5,8,1,3]
print(minimumDifference(nums)) # Output: 1function minimumDifference(nums) {
const n = nums.length / 3;
const prefixSum = new Array(3 * n + 1).fill(0);
const minHeap = [];
const maxHeap = [];
let suffixSum = nums.slice(2 * n).reduce((a, b) => a + b, 0);
let result = Infinity;
for (let i = 0; i < 3 * n; i++) {
minHeap.push(nums[i]);
minHeap.sort((a, b) => a - b);
if (minHeap.length > n) {
const removed = minHeap.shift();
prefixSum[i + 1] = prefixSum[i] + nums[i] - removed;
} else {
prefixSum[i + 1] = prefixSum[i] + nums[i];
}
}
for (let i = 0; i < n; i++) {
maxHeap.push(nums[3 * n - 1 - i]);
suffixSum -= nums[3 * n - 1 - i];
if (maxHeap.length > n) {
maxHeap.sort((a, b) => b - a);
const removed = maxHeap.shift();
suffixSum += removed;
}
result = Math.min(result, prefixSum[2 * n - i] - suffixSum);
}
return result;
}
const nums = [7, 9, 5, 8, 1, 3];
console.log(minimumDifference(nums)); // Output: 1This Python solution uses the prefix and suffix arrays to manage the sums efficiently. The prefix array stores the maximum sum of n numbers from the beginning of the array using a min-heap. Conversely, the suffix analysis maintains the minimum sum from the back using a max-heap. The difference between these prefix and suffix sums is calculated, and the minimum difference is returned.
Time Complexity: O(n log n), where n is the length of the array divided by 3.
Space Complexity: O(n) due to the storage of prefix and suffix data structures.
Approach 2: Sliding Window with Unordered Removal
In this approach, we leverage a sliding window technique to efficiently evaluate every possible subarray of length 2n using the 'unordered removal' strategy. The idea is to use prefix and suffix evaluations within a limited range in order to balance the parts optimally.
import java.util.*;
public class MinimumDifference {
public static int minimumDifference(int[] nums) {
int n = nums.length / 3;
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
long[] prefixSum = new long[3 * n + 1];
long suffixSum = 0;
long result = Long.MAX_VALUE;
for (int i = 2 * n; i < 3 * n; i++) {
suffixSum += nums[i];
}
for (int i = 0; i < 3 * n; i++) {
maxHeap.offer(nums[i]);
prefixSum[i + 1] = prefixSum[i] + nums[i];
if (maxHeap.size() > n) {
prefixSum[i + 1] -= maxHeap.poll();
}
}
for (int i = 0; i < n; i++) {
minHeap.offer(nums[3 * n - 1 - i]);
suffixSum -= nums[3 * n - 1 - i];
if (minHeap.size() > n) {
suffixSum += minHeap.poll();
}
result = Math.min(result, prefixSum[2 * n - i] - suffixSum);
}
return (int) result;
}
public static void main(String[] args) {
int[] nums = {7, 9, 5, 8, 1, 3};
System.out.println(minimumDifference(nums)); // Output: 1
}
}#include <iostream>
#include <vector>
#include <queue>
#include <numeric>
#include <algorithm>
int minimumDifference(std::vector<int>& nums) {
int n = nums.size() / 3;
std::priority_queue<int> maxHeap;
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
std::vector<long long> prefixSum(3 * n + 1, 0);
long long suffixSum = std::accumulate(nums.begin() + 2 * n, nums.end(), 0LL);
long long result = LLONG_MAX;
for (int i = 0; i < 3 * n; i++) {
maxHeap.push(nums[i]);
prefixSum[i + 1] = prefixSum[i] + nums[i];
if (maxHeap.size() > n) {
prefixSum[i + 1] -= maxHeap.top();
maxHeap.pop();
}
}
for (int i = 0; i < n; i++) {
minHeap.push(nums[3 * n - 1 - i]);
suffixSum -= nums[3 * n - 1 - i];
if (minHeap.size() > n) {
suffixSum += minHeap.top();
minHeap.pop();
}
result = std::min(result, prefixSum[2 * n - i] - suffixSum);
}
return result;
}
int main() {
std::vector<int> nums = {7, 9, 5, 8, 1, 3};
std::cout << minimumDifference(nums) << std::endl; // Output: 1
return 0;
}The main procedure here mirrors that of C++. This Java implementation processes input read and conversion into the necessary tracking structures, including priority queues. Through managed rotation via heaps, the solution calculates possible differences and tracks the minimal value.
Time Complexity: O(n log n) due to heap operations during splits.
Space Complexity: O(n) for state management.
Approach 3: Priority Queue (Max and Min Heap) + Prefix and Suffix Sum + Enumeration of Split Points
The problem is essentially equivalent to finding a split point in nums, dividing the array into two parts. In the first part, select the smallest n elements, and in the second part, select the largest n elements, so that the difference between the sums of the two parts is minimized.
We can use a max heap to maintain the smallest n elements in the prefix, and a min heap to maintain the largest n elements in the suffix. We define pre[i] as the sum of the smallest n elements among the first i elements of the array nums, and suf[i] as the sum of the largest n elements from the i-th element to the last element of the array. During the process of maintaining the max and min heaps, update the values of pre[i] and suf[i].
Finally, we enumerate the split points in the range of i \in [n, 2n], calculate the value of pre[i] - suf[i + 1], and take the minimum value.
The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the length of the array nums.
function minimumDifference(nums: number[]): number {
const m = nums.length;
const n = Math.floor(m / 3);
let s = 0;
const pre: number[] = Array(m + 1);
const q1 = new MaxPriorityQueue<number>();
for (let i = 1; i <= n * 2; ++i) {
const x = nums[i - 1];
s += x;
q1.enqueue(x);
if (q1.size() > n) {
s -= q1.dequeue();
}
pre[i] = s;
}
s = 0;
const suf: number[] = Array(m + 1);
const q2 = new MinPriorityQueue<number>();
for (let i = m; i > n; --i) {
const x = nums[i - 1];
s += x;
q2.enqueue(x);
if (q2.size() > n) {
s -= q2.dequeue();
}
suf[i] = s;
}
let ans = Number.MAX_SAFE_INTEGER;
for (let i = n; i <= n * 2; ++i) {
ans = Math.min(ans, pre[i] - suf[i + 1]);
}
return ans;
}func minimumDifference(nums []int) int64 {
m := len(nums)
n := m / 3
s := 0
pre := make([]int, m+1)
q1 := hp{}
for i := 1; i <= n*2; i++ {
x := nums[i-1]
s += x
heap.Push(&q1, -x)
if q1.Len() > n {
s -= -heap.Pop(&q1).(int)
}
pre[i] = s
}
s = 0
suf := make([]int, m+1)
q2 := hp{}
for i := m; i > n; i-- {
x := nums[i-1]
s += x
heap.Push(&q2, x)
if q2.Len() > n {
s -= heap.Pop(&q2).(int)
}
suf[i] = s
}
ans := int64(1e18)
for i := n; i <= n*2; i++ {
ans = min(ans, int64(pre[i]-suf[i+1]))
}
return ans
}
type hp struct{ sort.IntSlice }
func (h hp) Less(i, j int) bool { return h.IntSlice[i] < h.IntSlice[j] }
func (h *hp) Push(v any) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() any {
a := h.IntSlice
v := a[len(a)-1]
h.IntSlice = a[:len(a)-1]
return v
}use std::collections::BinaryHeap;
use std::cmp::Reverse;
impl Solution {
pub fn minimum_difference(nums: Vec<i32>) -> i64 {
let m = nums.len();
let n = m / 3;
let mut s = 0i64;
let mut pre = vec![0i64; m + 1];
let mut pq = BinaryHeap::new(); // max-heap
for i in 1..=2 * n {
let x = nums[i - 1] as i64;
s += x;
pq.push(x);
if pq.len() > n {
if let Some(top) = pq.pop() {
s -= top;
}
}
pre[i] = s;
}
s = 0;
let mut suf = vec![0i64; m + 1];
let mut pq = BinaryHeap::new();
for i in (n + 1..=m).rev() {
let x = nums[i - 1] as i64;
s += x;
pq.push(Reverse(x));
if pq.len() > n {
if let Some(Reverse(top)) = pq.pop() {
s -= top;
}
}
suf[i] = s;
}
let mut ans = i64::MAX;
for i in n..=2 * n {
ans = ans.min(pre[i] - suf[i + 1]);
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Prefix and Suffix Analysis with Priority Queues | Time Complexity: O(n log n), where n is the length of the array divided by 3. |
| Sliding Window with Unordered Removal | Time Complexity: O(n log n) due to heap operations during splits. |
| Priority Queue (Max and Min Heap) + Prefix and Suffix Sum + Enumeration of Split Points | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Prefix and Suffix Analysis with Priority Queues | O(n log n) | O(n) | General optimal solution. Works well for large arrays and is the most common interview approach. |
| Sliding Window with Unordered Removal | O(n log n) | O(n) | Useful when implementing dynamic boundary movement with ordered containers like multiset. |
Frequently asked questions
Is Minimum Difference in Sums After Removal of Elements easy or hard?
Minimum Difference in Sums After Removal of Elements is classified as a Hard problem. The difficulty comes from recognizing that the array must be analyzed from both directions and that heaps are required to maintain optimal subsets dynamically.
Minimum Difference in Sums After Removal of Elements Python/Java solution
Python solutions typically use heapq with negative values to simulate a max-heap and maintain prefix sums. Java implementations rely on PriorityQueue for both min-heap and max-heap behavior. Both follow the same prefix–suffix heap strategy with O(n log n) complexity.
How to solve Minimum Difference in Sums After Removal of Elements in O(n)?
A strict O(n) solution is not typical because maintaining the smallest or largest n elements dynamically requires ordered operations. The accepted optimal solution uses heaps, resulting in O(n log n) complexity. Attempts to remove the log factor usually require specialized structures that still behave like priority queues internally.
What is the best approach for Minimum Difference in Sums After Removal of Elements?
The most effective approach uses prefix and suffix analysis with priority queues. Maintain the smallest possible sum of n elements from the left using a max-heap, and the largest possible sum of n elements from the right using a min-heap. Precompute both arrays and evaluate every valid split. This solution runs in O(n log n) time and O(n) space.
Is Minimum Difference in Sums After Removal of Elements asked at Google/Amazon/Meta?
Problems combining prefix analysis with heap optimization appear frequently in interviews at companies like Google, Amazon, and Meta. Variants that require selecting optimal subsets while scanning an array are common in high-level system design and algorithm rounds.
What data structure is used in Minimum Difference in Sums After Removal of Elements?
Priority queues (heaps) are the key data structure. A max-heap tracks the n smallest elements for the prefix calculation, while a min-heap tracks the n largest elements for the suffix calculation. These structures allow efficient push and pop operations during the scan.
What is the time complexity of Minimum Difference in Sums After Removal of Elements?
The optimal solution runs in O(n log n) time where n is one third of the array length (the array has 3n elements). Heap insert and removal operations dominate the complexity. Space complexity is O(n) because prefix and suffix arrays store intermediate sums.