Skip to main content
Talentd

Minimum Difference in Sums After Removal of Elements - Solution & Explanation

HardArrayDynamic ProgrammingHeap (Priority Queue)19 min readAsked at: Amazon, Microsoft, Meta +4
Practice this problem

Problem Statement

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.

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 * n
  • 1 <= n <= 105
  • 1 <= 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.

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.

Code

PythonJavaScript

Python

JavaScript

Complexity

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.

Try this approach in the editor →

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.

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.

Code

C++Java

C++

Java

Complexity

Time Complexity: O(n log n) due to heap operations over splits.
Space Complexity: O(n) for auxiliary storage.

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Prefix and Suffix Analysis with Priority Queues

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.

Sliding Window with Unordered Removal

Time Complexity: O(n log n) due to heap operations over splits.
Space Complexity: O(n) for auxiliary storage.

Priority Queue (Max and Min Heap) + Prefix and Suffix Sum + Enumeration of Split Points—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Prefix and Suffix Analysis with Priority QueuesO(n log n)O(n)General optimal solution. Works well for large arrays and is the most common interview approach.
Sliding Window with Unordered RemovalO(n log n)O(n)Useful when implementing dynamic boundary movement with ordered containers like multiset.

Video Solution

Minimum Difference in Sums After Removal of Elements | Detailed Explanation | Leetcode 2163 | MIK • codestorywithMIK • 10,142 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Minimum Difference in Sums After Removal of Elements with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find Minimum Cost to Remove Array Elements

Next

Find Subsequence of Length K With the Largest Sum