Minimum Difference in Sums After Removal of Elements

Hard

#1970Time: O(n^2 * log n). The main loop runs `n+1` times. Inside the loop, sorting arrays of size up to `O(n)` takes `O(n log n)` time, leading to a total complexity of `O(n * (n log n))`.Space: O(n), for storing the prefix and suffix subarrays in each iteration. The size of these subarrays can be up to `2n`.

Patterns

Dynamic Programming

Data structures

Array Heap (Priority Queue)

Prompt

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 sum_first.
The next n elements belonging to the second part and their sum is sum_second.

The difference in sums of the two parts is denoted as sum_first - sum_second.

For example, if sum_first = 3 and sum_second = 2, their difference is 1.
Similarly, if sum_first = 2 and sum_second = 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 <= 10⁵
1 <= nums[i] <= 10⁵

Approaches

2 approaches with complexity analysis and trade-offs.

This approach iterates through all possible ways to partition the original array into a prefix and a suffix, from which the two parts of the final array will be formed. For each partition, it calculates the required sums by sorting the prefix and suffix subarrays.

Algorithm

Initialize min_diff to a very large value.
Iterate through all possible split points i from n to 2*n.
For each i:
- Create a prefix subarray nums[0...i-1].
- Sort the prefix subarray.
- Calculate sum_first by summing the first n (smallest) elements.
- Create a suffix subarray nums[i...3*n-1].
- Sort the suffix subarray.
- Calculate sum_second by summing the last n (largest) elements.
- Update min_diff = min(min_diff, sum_first - sum_second).
Return min_diff.

Walkthrough

The core idea is to recognize that the final 2n elements are formed by taking n elements from a prefix nums[0...i-1] and n elements from a suffix nums[i...3n-1] of the original array, preserving relative order. The split point i can range from n to 2n.

To minimize sum_first - sum_second, we must select the n smallest elements for the first part and the n largest elements for the second part.

The algorithm iterates through each possible split index i from n to 2n. In each iteration:

It takes the prefix nums[0...i-1].
It sorts this prefix and sums up the first n elements to get sum_first.
It takes the suffix nums[i...3n-1].
It sorts this suffix and sums up the last n elements (the largest ones) to get sum_second.
It calculates the difference sum_first - sum_second and updates the overall minimum difference.

This process is repeated for all valid split points, and the minimum difference found is the result.

1import java.util.Arrays;2 3class Solution {4    public long minimumDifference(int[] nums) {5        int totalSize = nums.length;6        int n = totalSize / 3;7        long minDiff = Long.MAX_VALUE;8 9        for (int i = n; i <= 2 * n; i++) {10            // Create and sort prefix11            int[] prefix = Arrays.copyOfRange(nums, 0, i);12            Arrays.sort(prefix);13            long sumFirst = 0;14            for (int j = 0; j < n; j++) {15                sumFirst += prefix[j];16            }17 18            // Create and sort suffix19            int[] suffix = Arrays.copyOfRange(nums, i, totalSize);20            Arrays.sort(suffix);21            long sumSecond = 0;22            for (int j = 0; j < n; j++) {23                sumSecond += suffix[suffix.length - 1 - j];24            }25            26            minDiff = Math.min(minDiff, sumFirst - sumSecond);27        }28        return minDiff;29    }30}

Complexity

Time

O(n^2 * log n). The main loop runs `n+1` times. Inside the loop, sorting arrays of size up to `O(n)` takes `O(n log n)` time, leading to a total complexity of `O(n * (n log n))`.

Space

O(n), for storing the prefix and suffix subarrays in each iteration. The size of these subarrays can be up to `2n`.

Trade-offs

Pros

Conceptually simple and easy to understand.
Directly translates the problem definition into code.

Cons

Highly inefficient due to repeated sorting of overlapping subarrays.
Will result in a 'Time Limit Exceeded' error for the given constraints.

This is an optimized approach that avoids re-computation by pre-calculating the possible values for sum_first and sum_second for all split points. It uses heaps (priority queues) to efficiently maintain the sum of the n smallest/largest elements as we iterate through the array.

Algorithm

Let N = nums.length and n = N / 3.
Create a prefix_min_sum array. Use a max-heap of size n to iterate from left to right, calculating the sum of the n smallest elements in nums[0...i] and storing it in prefix_min_sum[i].
Create a suffix_max_sum array. Use a min-heap of size n to iterate from right to left, calculating the sum of the n largest elements in nums[i...N-1] and storing it in suffix_max_sum[i].
Initialize min_diff to a very large value.
Iterate i from n to 2*n:
- The first part's sum is prefix_min_sum[i-1] (sum of n smallest from nums[0...i-1]).
- The second part's sum is suffix_max_sum[i] (sum of n largest from nums[i...N-1]).
- Update min_diff = min(min_diff, prefix_min_sum[i-1] - suffix_max_sum[i]).
Return min_diff.

Walkthrough

The problem can be broken down into finding min(min_sum_prefix(i-1) - max_sum_suffix(i)) for all valid split points i from n to 2n.

min_sum_prefix(k) is the sum of the n smallest elements in nums[0...k].
max_sum_suffix(k) is the sum of the n largest elements in nums[k...3n-1].

We can compute all necessary min_sum_prefix values in a single forward pass and all max_sum_suffix values in a single backward pass.

Forward Pass (for sum_first): We iterate from left to right, using a max-heap of size n to keep track of the n smallest elements seen so far. As we iterate to index k, we add nums[k] to the heap. If the heap size exceeds n, we remove the largest element. We maintain a running sum of elements in the heap and store these sums in a prefix_min_sum array.

Backward Pass (for sum_second): We iterate from right to left, using a min-heap of size n to keep track of the n largest elements seen so far. The logic is similar: as we iterate to index k from the right, we add nums[k] to the heap and remove the smallest if the size exceeds n. We store these sums in a suffix_max_sum array.

Final Calculation: After pre-computation, we iterate through all possible split points i from n to 2n. For each i, the difference is prefix_min_sum[i-1] - suffix_max_sum[i]. We find the minimum among all these differences.

1import java.util.PriorityQueue;2import java.util.Collections;3 4class Solution {5    public long minimumDifference(int[] nums) {6        int totalSize = nums.length;7        int n = totalSize / 3;8 9        long[] prefix_min_sum = new long[totalSize];10        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());11        long currentSum = 0;12 13        for (int i = 0; i < totalSize; i++) {14            maxHeap.add(nums[i]);15            currentSum += nums[i];16            if (maxHeap.size() > n) {17                currentSum -= maxHeap.poll();18            }19            if (maxHeap.size() == n) {20                prefix_min_sum[i] = currentSum;21            }22        }23 24        long[] suffix_max_sum = new long[totalSize];25        PriorityQueue<Integer> minHeap = new PriorityQueue<>();26        currentSum = 0;27 28        for (int i = totalSize - 1; i >= 0; i--) {29            minHeap.add(nums[i]);30            currentSum += nums[i];31            if (minHeap.size() > n) {32                currentSum -= minHeap.poll();33            }34            if (minHeap.size() == n) {35                suffix_max_sum[i] = currentSum;36            }37        }38 39        long minDiff = Long.MAX_VALUE;40        for (int i = n; i <= 2 * n; i++) {41            long sumFirst = prefix_min_sum[i - 1];42            long sumSecond = suffix_max_sum[i];43            minDiff = Math.min(minDiff, sumFirst - sumSecond);44        }45 46        return minDiff;47    }48}

Complexity

Time

O(n log n). The forward pass to compute `prefix_min_sum` takes `O(3n * log n)`. The backward pass for `suffix_max_sum` also takes `O(3n * log n)`. The final loop takes `O(n)`. The dominant factor is `O(n log n)`.

Space

O(n). We use two arrays of size `3n` (`prefix_min_sum`, `suffix_max_sum`) and two heaps of size `n`. This all amounts to `O(n)` space.

Trade-offs

Pros

Highly efficient and passes the given constraints.
Effectively uses heaps to avoid redundant calculations, following a dynamic programming-like pattern of pre-computation.

Cons

More complex to implement than the brute-force approach.
Requires careful handling of indices and heap logic.

Solutions

Solution

1class Solution {2public3  long minimumDifference(int[] nums) {4    int m = nums.length;5    int n = m / 3;6    long s = 0;7    long[] pre = new long[m + 1];8    PriorityQueue<Integer> pq = new PriorityQueue<>((a, b)->b - a);9    for (int i = 1; i <= n * 2; ++i) {10      int x = nums[i - 1];11      s += x;12      pq.offer(x);13      if (pq.size() > n) {14        s -= pq.poll();15      }16      pre[i] = s;17    }18    s = 0;19    long[] suf = new long[m + 1];20    pq = new PriorityQueue<>();21    for (int i = m; i > n; --i) {22      int x = nums[i - 1];23      s += x;24      pq.offer(x);25      if (pq.size() > n) {26        s -= pq.poll();27      }28      suf[i] = s;29    }30    long ans = 1L << 60;31    for (int i = n; i <= n * 2; ++i) {32      ans = Math.min(ans, pre[i] - suf[i + 1]);33    }34    return ans;35  }36}

1class Solution {2public:3  long long minimumDifference(vector<int> &nums) {4    int m = nums.size();5    int n = m / 3;6    using ll = long long;7    ll s = 0;8    ll pre[m + 1];9    priority_queue<int> q1;10    for (int i = 1; i <= n * 2; ++i) {11      int x = nums[i - 1];12      s += x;13      q1.push(x);14      if (q1.size() > n) {15        s -= q1.top();16        q1.pop();17      }18      pre[i] = s;19    }20    s = 0;21    ll suf[m + 1];22    priority_queue<int, vector<int>, greater<int>> q2;23    for (int i = m; i > n; --i) {24      int x = nums[i - 1];25      s += x;26      q2.push(x);27      if (q2.size() > n) {28        s -= q2.top();29        q2.pop();30      }31      suf[i] = s;32    }33    ll ans = 1e18;34    for (int i = n; i <= n * 2; ++i) {35      ans = min(ans, pre[i] - suf[i + 1]);36    }37    return ans;38  }39};

1class Solution:2    def minimumDifference(self, nums: List[int]) -> int: m = len(nums) n = m // 3 s = 0 pre = [0] * (m + 1) q1 = [] for i, x in enumerate(nums[: n * 2], 1): s += x heappush(q1, - x) if len(q1) > n: s -= - heappop(q1) pre[i] = s s = 0 suf = [0] * (m + 1) q2 = [] for i in range(m, n, - 1): x = nums[i - 1] s += x heappush(q2, x) if len(q2) > n: s -= heappop(q2) suf[i] = s return min(pre[i] - suf[i + 1] for i in range(n, n * 2 + 1))

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem