# Minimum Difference in Sums After Removal of Elements
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-difference-in-sums-after-removal-of-elements)
Canonical: https://scaleengineer.com/dsa/problems/minimum-difference-in-sums-after-removal-of-elements
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array, Heap (Priority Queue)
---
## 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 `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`

# Approaches
## Brute Force with Sorting for each Split Point
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.
**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`.
**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.
### Explanation
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:
1. It takes the prefix `nums[0...i-1]`.
2. It sorts this prefix and sums up the first `n` elements to get `sum_first`.
3. It takes the suffix `nums[i...3n-1]`.
4. It sorts this suffix and sums up the last `n` elements (the largest ones) to get `sum_second`.
5. 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.

```java
import java.util.Arrays;

class Solution {
    public long minimumDifference(int[] nums) {
        int totalSize = nums.length;
        int n = totalSize / 3;
        long minDiff = Long.MAX_VALUE;

        for (int i = n; i <= 2 * n; i++) {
            // Create and sort prefix
            int[] prefix = Arrays.copyOfRange(nums, 0, i);
            Arrays.sort(prefix);
            long sumFirst = 0;
            for (int j = 0; j < n; j++) {
                sumFirst += prefix[j];
            }

            // Create and sort suffix
            int[] suffix = Arrays.copyOfRange(nums, i, totalSize);
            Arrays.sort(suffix);
            long sumSecond = 0;
            for (int j = 0; j < n; j++) {
                sumSecond += suffix[suffix.length - 1 - j];
            }
            
            minDiff = Math.min(minDiff, sumFirst - sumSecond);
        }
        return minDiff;
    }
}
```
### 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`.

## Prefix/Suffix Sums with Heaps
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.
**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.
**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.
### Explanation
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.

```java
import java.util.PriorityQueue;
import java.util.Collections;

class Solution {
    public long minimumDifference(int[] nums) {
        int totalSize = nums.length;
        int n = totalSize / 3;

        long[] prefix_min_sum = new long[totalSize];
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        long currentSum = 0;

        for (int i = 0; i < totalSize; i++) {
            maxHeap.add(nums[i]);
            currentSum += nums[i];
            if (maxHeap.size() > n) {
                currentSum -= maxHeap.poll();
            }
            if (maxHeap.size() == n) {
                prefix_min_sum[i] = currentSum;
            }
        }

        long[] suffix_max_sum = new long[totalSize];
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        currentSum = 0;

        for (int i = totalSize - 1; i >= 0; i--) {
            minHeap.add(nums[i]);
            currentSum += nums[i];
            if (minHeap.size() > n) {
                currentSum -= minHeap.poll();
            }
            if (minHeap.size() == n) {
                suffix_max_sum[i] = currentSum;
            }
        }

        long minDiff = Long.MAX_VALUE;
        for (int i = n; i <= 2 * n; i++) {
            long sumFirst = prefix_min_sum[i - 1];
            long sumSecond = suffix_max_sum[i];
            minDiff = Math.min(minDiff, sumFirst - sumSecond);
        }

        return minDiff;
    }
}
```
### 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`.

# Solutions
### Java

```java
class Solution {
public
  long minimumDifference(int[] nums) {
    int m = nums.length;
    int n = m / 3;
    long s = 0;
    long[] pre = new long[m + 1];
    PriorityQueue<Integer> pq = new PriorityQueue<>((a, b)->b - a);
    for (int i = 1; i <= n * 2; ++i) {
      int x = nums[i - 1];
      s += x;
      pq.offer(x);
      if (pq.size() > n) {
        s -= pq.poll();
      }
      pre[i] = s;
    }
    s = 0;
    long[] suf = new long[m + 1];
    pq = new PriorityQueue<>();
    for (int i = m; i > n; --i) {
      int x = nums[i - 1];
      s += x;
      pq.offer(x);
      if (pq.size() > n) {
        s -= pq.poll();
      }
      suf[i] = s;
    }
    long ans = 1L << 60;
    for (int i = n; i <= n * 2; ++i) {
      ans = Math.min(ans, pre[i] - suf[i + 1]);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long minimumDifference(vector<int> &nums) {
    int m = nums.size();
    int n = m / 3;
    using ll = long long;
    ll s = 0;
    ll pre[m + 1];
    priority_queue<int> q1;
    for (int i = 1; i <= n * 2; ++i) {
      int x = nums[i - 1];
      s += x;
      q1.push(x);
      if (q1.size() > n) {
        s -= q1.top();
        q1.pop();
      }
      pre[i] = s;
    }
    s = 0;
    ll suf[m + 1];
    priority_queue<int, vector<int>, greater<int>> q2;
    for (int i = m; i > n; --i) {
      int x = nums[i - 1];
      s += x;
      q2.push(x);
      if (q2.size() > n) {
        s -= q2.top();
        q2.pop();
      }
      suf[i] = s;
    }
    ll ans = 1e18;
    for (int i = n; i <= n * 2; ++i) {
      ans = min(ans, pre[i] - suf[i + 1]);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    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))

```