Minimum Difference in Sums After Removal of Elements

hard heap prefix / suffix greedy

Problem

You are given an array nums of 3n elements. Remove any subsequence of exactly n elements. The remaining 2n elements keep their order: the first n form part one with sum sum_first, the next n form part two with sum sum_second. Return the minimum possible value of sum_first − sum_second.

To minimize the difference we want sum_first as small as possible and sum_second as large as possible. Choose a split index i: take the smallest n values from the prefix nums[0..i) and the largest n values from the suffix nums[i..3n). A size-n max-heap streams the prefix minimum, a size-n min-heap streams the suffix maximum.

Inputnums = [7,9,5,8,1,3]

Output1

n = 2. Remove 9 and 1, leaving [7,5,8,3]: (7+5) − (8+3) = 12 − 11 = 1, the smallest achievable.

nums (comma-separated, length must be a multiple of 3)

import heapq

def minimumDifference(nums):
    m = len(nums); n = m // 3
    # pref[i] = min sum of n elements among nums[0:i]
    pref = [0] * (m + 1)
    max_heap = []        # negatives: keeps the smallest n seen
    s = 0
    for i in range(2 * n):
        heapq.heappush(max_heap, -nums[i]); s += nums[i]
        if len(max_heap) > n:
            s += heapq.heappop(max_heap)   # drop the largest kept
        if len(max_heap) == n:
            pref[i + 1] = s
    # suf[i] = max sum of n elements among nums[i:m]
    suf = [0] * (m + 1)
    min_heap = []        # keeps the largest n seen
    s = 0
    for i in range(m - 1, n - 1, -1):
        heapq.heappush(min_heap, nums[i]); s += nums[i]
        if len(min_heap) > n:
            s -= heapq.heappop(min_heap)   # drop the smallest kept
        if len(min_heap) == n:
            suf[i] = s
    ans = float('inf')
    for i in range(n, 2 * n + 1):          # split point
        ans = min(ans, pref[i] - suf[i])
    return ans

function minimumDifference(nums) {
  const m = nums.length, n = (m / 3) | 0;
  const pref = new Array(m + 1).fill(0);
  const maxHeap = new MaxHeap();        // keeps the smallest n
  let s = 0;
  for (let i = 0; i < 2 * n; i++) {
    maxHeap.push(nums[i]); s += nums[i];
    if (maxHeap.size() > n) s -= maxHeap.pop();   // drop largest kept
    if (maxHeap.size() === n) pref[i + 1] = s;
  }
  const suf = new Array(m + 1).fill(0);
  const minHeap = new MinHeap();        // keeps the largest n
  s = 0;
  for (let i = m - 1; i >= n; i--) {
    minHeap.push(nums[i]); s += nums[i];
    if (minHeap.size() > n) s -= minHeap.pop();   // drop smallest kept
    if (minHeap.size() === n) suf[i] = s;
  }
  let ans = Infinity;
  for (let i = n; i <= 2 * n; i++)       // split point
    ans = Math.min(ans, pref[i] - suf[i]);
  return ans;
}

long minimumDifference(int[] nums) {
    int m = nums.length, n = m / 3;
    long[] pref = new long[m + 1];
    PriorityQueue<Integer> maxHeap =     // keeps the smallest n
        new PriorityQueue<>(Collections.reverseOrder());
    long s = 0;
    for (int i = 0; i < 2 * n; i++) {
        maxHeap.add(nums[i]); s += nums[i];
        if (maxHeap.size() > n) s -= maxHeap.poll();  // drop largest
        if (maxHeap.size() == n) pref[i + 1] = s;
    }
    long[] suf = new long[m + 1];
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    s = 0;
    for (int i = m - 1; i >= n; i--) {
        minHeap.add(nums[i]); s += nums[i];
        if (minHeap.size() > n) s -= minHeap.poll();  // drop smallest
        if (minHeap.size() == n) suf[i] = s;
    }
    long ans = Long.MAX_VALUE;
    for (int i = n; i <= 2 * n; i++)      // split point
        ans = Math.min(ans, pref[i] - suf[i]);
    return ans;
}

long long minimumDifference(vector<int>& nums) {
    int m = nums.size(), n = m / 3;
    vector<long long> pref(m + 1, 0), suf(m + 1, 0);
    priority_queue<int> maxHeap;          // keeps the smallest n
    long long s = 0;
    for (int i = 0; i < 2 * n; i++) {
        maxHeap.push(nums[i]); s += nums[i];
        if ((int)maxHeap.size() > n) { s -= maxHeap.top(); maxHeap.pop(); }
        if ((int)maxHeap.size() == n) pref[i + 1] = s;
    }
    priority_queue<int, vector<int>, greater<int>> minHeap;
    s = 0;
    for (int i = m - 1; i >= n; i--) {
        minHeap.push(nums[i]); s += nums[i];
        if ((int)minHeap.size() > n) { s -= minHeap.top(); minHeap.pop(); }
        if ((int)minHeap.size() == n) suf[i] = s;
    }
    long long ans = LLONG_MAX;
    for (int i = n; i <= 2 * n; i++)      // split point
        ans = min(ans, pref[i] - suf[i]);
    return ans;
}

Explanation

Removing n elements and splitting the rest is equivalent to picking a split index i: every kept element of part one comes from the prefix nums[0..i) and every kept element of part two comes from the suffix nums[i..3n). We need exactly n elements on each side, so i ranges from n to 2n.

For a fixed split, the best move is independent on the two sides: choose the smallest n prefix values to make sum_first minimal, and the largest n suffix values to make sum_second maximal. The order constraint is automatically satisfied because prefix indices are all below suffix indices.

To compute these for every split in one sweep we use heaps. Scanning left to right, a max-heap of size n holds the smallest n values seen so far: whenever it overflows we pop the largest, and pref[i] records the running sum of those n smallest values. Scanning right to left, a min-heap of size n holds the largest n values; popping the smallest on overflow gives suf[i].

Finally we slide the split index over i = n .. 2n and take min(pref[i] - suf[i]). Each heap operation is O(log n) and we do O(n) of them, so the whole solution is O(n log n).

Example [7,9,5,8,1,3] (n = 2): the best split keeps {7,5} on the left and {8,3} on the right after dropping 9 and 1, giving 12 − 11 = 1.

Time: O(n log n) Space: O(n)