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 _theminimum difference possible between the sums of the two parts after the removal of _n elements.

Examples

Example 1

1
2
3
4
5
6
7
8

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

1
2
3
4
5
6

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^5
  • 1 <= nums[i] <= 10^5

Solution

Method 1 – Heap Optimization for Prefix and Suffix Sums

Intuition

To minimize the difference, we want the largest possible sum for the first part and the smallest possible sum for the second part after removing n elements. We use heaps to efficiently track the best n elements to remove from each side.

Approach

  1. Let n = nums.length / 3.
  2. For the first 2n elements, use a max-heap to keep the smallest n elements (for prefix sum).
  3. For the last 2n elements, use a min-heap to keep the largest n elements (for suffix sum).
  4. For each split point, calculate the difference between the prefix and suffix sums.
  5. Return the minimum difference found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class Solution {
public:
    long long minimumDifference(vector<int>& nums) {
        int n = nums.size() / 3;
        priority_queue<int> maxh;
        vector<long long> left(n * 2 + 1);
        long long sum = 0;
        for (int i = 0; i < n * 2; ++i) {
            sum += nums[i];
            maxh.push(nums[i]);
            if (maxh.size() > n) {
                sum -= maxh.top();
                maxh.pop();
            }
            left[i + 1] = sum;
        }
        priority_queue<int, vector<int>, greater<int>> minh;
        vector<long long> right(n * 2 + 1);
        sum = 0;
        for (int i = nums.size() - 1; i >= n; --i) {
            sum += nums[i];
            minh.push(nums[i]);
            if (minh.size() > n) {
                sum -= minh.top();
                minh.pop();
            }
            right[i - n] = sum;
        }
        long long ans = LLONG_MAX;
        for (int i = n; i <= n * 2; ++i) {
            ans = min(ans, left[i] - right[i]);
        }
        return ans;
    }
};
1

// Skipped for brevity due to heap implementation complexity in Go.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

class Solution {
    public long minimumDifference(int[] nums) {
        int n = nums.length / 3;
        PriorityQueue<Long> maxh = new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Long> minh = new PriorityQueue<>();
        List<Long> left = new ArrayList<>();
        List<Long> right = new ArrayList<>();
        long sum = 0;
        for (int i = 0; i < n; i++) {
            maxh.add((long)nums[i]);
            sum += nums[i];
        }
        left.add(sum);
        for (int i = n; i < 2 * n; i++) {
            maxh.add((long)nums[i]);
            sum += nums[i];
            sum -= maxh.poll();
            left.add(sum);
        }
        sum = 0;
        for (int i = 3 * n - 1; i >= 2 * n; i--) {
            minh.add((long)nums[i]);
            sum += nums[i];
        }
        right.add(sum);
        for (int i = 2 * n - 1; i >= n; i--) {
            minh.add((long)nums[i]);
            sum += nums[i];
            sum -= minh.poll();
            right.add(sum);
        }
        Collections.reverse(right);
        long ans = Long.MAX_VALUE;
        for (int i = 0; i < left.size(); i++) {
            ans = Math.min(ans, left.get(i) - right.get(i));
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution {
    fun minimumDifference(nums: IntArray): Long {
        val n = nums.size / 3
        val maxh = PriorityQueue<Int>(compareByDescending { it })
        val left = LongArray(n * 2 + 1)
        var sum = 0L
        for (i in 0 until n * 2) {
            sum += nums[i]
            maxh.add(nums[i])
            if (maxh.size > n) {
                sum -= maxh.poll()
            }
            left[i + 1] = sum
        }
        val minh = PriorityQueue<Int>()
        val right = LongArray(n * 2 + 1)
        sum = 0L
        for (i in nums.size - 1 downTo n) {
            sum += nums[i]
            minh.add(nums[i])
            if (minh.size > n) {
                sum -= minh.poll()
            }
            right[i - n] = sum
        }
        var ans = Long.MAX_VALUE
        for (i in n..n * 2) {
            ans = minOf(ans, left[i] - right[i])
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

def minimum_difference(nums: list[int]) -> int:
    import heapq
    n = len(nums) // 3
    maxh, minh = [], []
    left = [0] * (2 * n + 1)
    s = 0
    for i in range(2 * n):
        s += nums[i]
        heapq.heappush(maxh, -nums[i])
        if len(maxh) > n:
            s += heapq.heappop(maxh)
        left[i + 1] = s
    right = [0] * (2 * n + 1)
    s = 0
    for i in range(len(nums) - 1, n - 1, -1):
        s += nums[i]
        heapq.heappush(minh, nums[i])
        if len(minh) > n:
            s -= heapq.heappop(minh)
        right[i - n] = s
    ans = float('inf')
    for i in range(n, 2 * n + 1):
        ans = min(ans, left[i] - right[i])
    return ans
1

// Skipped for brevity due to heap implementation complexity in Rust.

1

// Skipped for brevity due to heap implementation complexity in TypeScript.

Complexity

  • ⏰ Time complexity: O(n log n), for maintaining heaps and traversing the array.
  • 🧺 Space complexity: O(n), for prefix/suffix arrays and heaps.