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:
n elements belonging to the first part and their sum is sumfirst.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.
sumfirst = 3 and sumsecond = 2, their difference is 1.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.
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] <= 105Problem 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.
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.
This 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.
Python
JavaScript
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.
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.
The C++ implementation proposes a more direct manipulation of the problem using two priority queues to track and update necessary elements. By processing elements in window-like advances, you can guarantee that the window will contain the necessary average values to balance itself for two parts after n removals.
Time Complexity: O(n log n) due to heap operations over splits.
Space Complexity: O(n) for auxiliary storage.
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.
| 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 over splits. |
| Priority Queue (Max and Min Heap) + Prefix and Suffix Sum + Enumeration of Split Points | — |
| 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. |
Minimum Difference in Sums After Removal of Elements | Detailed Explanation | Leetcode 2163 | MIK • codestorywithMIK • 9,555 views views
Watch 9 more video solutions →Practice Minimum Difference in Sums After Removal of Elements with our built-in code editor and test cases.
Practice on FleetCode