Minimum Difference in Sums After Removal of Elements

Hard
1431.

Minimum Difference in Sums After Removal of Elements

HardArrayDynamic ProgrammingHeap (Priority Queue)GoogleAmazon

Minimum Difference in Sums After Removal of Elements is a hard coding problem on arrays, dynamic programming and heap, asked in Amazon and Google interviews.

You are given an array nums of 3 * n elements.

Remove any n of them (they need not be contiguous). The 2 * n elements that remain keep their order and are split in two: the first n form the first part, with sum sumfirst, and the last n form the second part, with sum sumsecond.

The difference of the split is sumfirst - sumsecond. Return the minimum difference you can achieve.

Constraint note: values are capped at 10^4 (the original allows 10^5) so every sum fits in a 32-bit integer.

Example 1

Input
nums = [4,1,6,2,8,3]
Output
-9
Explanation
Remove 2 and 3: the remaining [4,1,6,8] splits into [4,1] (sum 5) and [6,8] (sum 14).

Example 2

Input
nums = [3,1,2]
Output
-1
Explanation
Remove 3: the parts are [1] and [2].

Example 3

Input
nums = [7,9,5,8,1,3]
Output
1

Constraints

  • nums.length == 3 * n
  • 1 <= n <= 10^5
  • 1 <= nums[i] <= 10^4
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var minimumDifference = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Difference in Sums After Removal of Elements Solution

Minimum Difference in Sums After Removal of Elements solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Minimum Difference in Sums After Removal of Elements is a hard coding problem on arrays, dynamic programming and heap, asked in Amazon and Google interviews.

  • Difficulty: Hard
  • Topics: Arrays, Dynamic Programming, Heap
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given an array nums of 3 * n elements.

Remove any n of them (they need not be contiguous). The 2 * n elements that remain keep their order and are split in two: the first n form the first part, with sum sumfirst, and the last n form the second part, with sum sumsecond.

The difference of the split is sumfirst - sumsecond. Return the minimum difference you can achieve.

Constraint note: values are capped at 10^4 (the original allows 10^5) so every sum fits in a 32-bit integer.

Example 1

Input: nums = [4,1,6,2,8,3]
Output: -9
Explanation: Remove 2 and 3: the remaining [4,1,6,8] splits into [4,1] (sum 5) and [6,8] (sum 14).

Example 2

Input: nums = [3,1,2]
Output: -1
Explanation: Remove 3: the parts are [1] and [2].

Example 3

Input: nums = [7,9,5,8,1,3]
Output: 1

Constraints

  • nums.length == 3 * n
  • 1 <= n <= 10^5
  • 1 <= nums[i] <= 10^4

Hints for Minimum Difference in Sums After Removal of Elements

  1. Hint 1

    After the removal there is a cut position k with n <= k <= 2n: the first part comes from nums[0..k) and the second from nums[k..3n).

  2. Hint 2

    For a fixed cut, the first part should be the n smallest values of the prefix and the second part the n largest of the suffix.

  3. Hint 3

    Compute the best prefix sum for every cut with a max-heap of size n (evict the largest), and the best suffix sum with a min-heap of size n scanning from the right.

How to solve Minimum Difference in Sums After Removal of Elements

Fix the boundary k between the two parts. Then the parts are independent: minimise the first by keeping the n smallest of nums[0..k), maximise the second by keeping the n largest of nums[k..3n). Both families of answers come from one sweep each with a bounded heap.

Approach

  1. Left sweep: start with the first n values in a max-heap and their sum as left[n]. For i = n .. 2n-1, push nums[i], pop the largest and update the sum; record left[i+1].
  2. Right sweep: start with the last n values in a min-heap and their sum as right[2n]. For i = 2n-1 down to n, push nums[i], pop the smallest and update the sum; record right[i].
  3. Return the minimum of left[k] - right[k] over k = n .. 2n.

Why it works

Any valid removal leaves a first part entirely before a second part, so some k in [n, 2n] separates them, and for that k the choice inside each side is unconstrained — the extremal n values are optimal. The bounded heaps maintain exactly those extremal sets as the boundary moves one step at a time.

Complexity

  • Time — O(n log n)
  • Space — O(n)

Pitfalls

  • The cut ranges over n + 1 positions, both ends included.
  • The left side needs the n smallest (evict the maximum), the right side the n largest (evict the minimum) — swapping them maximises the difference instead.
  • With the original limits the sums exceed 32 bits; accumulate in 64-bit where the language needs it.

Reference solution

Python

from typing import List
import heapq

def minimumDifference(nums: List[int]) -> int:
    n = len(nums) // 3
    # left[i]: least sum of n values among nums[:n + i]
    heap = [-v for v in nums[:n]]
    heapq.heapify(heap)
    s = sum(nums[:n])
    left = [s]
    for i in range(n, 2 * n):
        s += nums[i]
        heapq.heappush(heap, -nums[i])
        s += heapq.heappop(heap)  # evict the largest
        left.append(s)
    # sweep the cut from 2n down to n with the n largest values of the suffix
    heap = nums[2 * n:]
    heapq.heapify(heap)
    s = sum(heap)
    best = left[n] - s
    for i in range(2 * n - 1, n - 1, -1):
        s += nums[i]
        heapq.heappush(heap, nums[i])
        s -= heapq.heappop(heap)  # evict the smallest
        best = min(best, left[i - n] - s)
    return best

Java

public static int minimumDifference(int[] nums) {
    int n = nums.length / 3;
    long[] left = new long[n + 1];
    PriorityQueue<Integer> low = new PriorityQueue<>(Collections.reverseOrder());
    long sum = 0;
    for (int i = 0; i < n; i++) {
        low.add(nums[i]);
        sum += nums[i];
    }
    left[0] = sum;
    for (int i = n; i < 2 * n; i++) {
        low.add(nums[i]);
        sum += nums[i] - low.poll(); // evict the largest
        left[i - n + 1] = sum;
    }
    PriorityQueue<Integer> high = new PriorityQueue<>();
    sum = 0;
    for (int i = 2 * n; i < 3 * n; i++) {
        high.add(nums[i]);
        sum += nums[i];
    }
    long best = left[n] - sum;
    for (int i = 2 * n - 1; i >= n; i--) {
        high.add(nums[i]);
        sum += nums[i] - high.poll(); // evict the smallest
        best = Math.min(best, left[i - n] - sum);
    }
    return (int) best;
}

C++

int minimumDifference(vector<int>& nums) {
    int n = nums.size() / 3;
    vector<long long> left(n + 1);
    priority_queue<int> low;
    long long sum = 0;
    for (int i = 0; i < n; i++) {
        low.push(nums[i]);
        sum += nums[i];
    }
    left[0] = sum;
    for (int i = n; i < 2 * n; i++) {
        low.push(nums[i]);
        sum += nums[i] - low.top(); // evict the largest
        low.pop();
        left[i - n + 1] = sum;
    }
    priority_queue<int, vector<int>, greater<int>> high;
    sum = 0;
    for (int i = 2 * n; i < 3 * n; i++) {
        high.push(nums[i]);
        sum += nums[i];
    }
    long long best = left[n] - sum;
    for (int i = 2 * n - 1; i >= n; i--) {
        high.push(nums[i]);
        sum += nums[i] - high.top(); // evict the smallest
        high.pop();
        best = min(best, left[i - n] - sum);
    }
    return (int) best;
}

JavaScript

var minimumDifference = function(nums) {
    var n = nums.length / 3;
    // left[i]: least sum of n values among the first n + i (max-heap via negation)
    var low = [];
    var sum = 0;
    for (var i = 0; i < n; i++) {
        heapPush(low, -nums[i]);
        sum += nums[i];
    }
    var left = [sum];
    for (var i2 = n; i2 < 2 * n; i2++) {
        heapPush(low, -nums[i2]);
        sum += nums[i2] + heapPop(low); // evict the largest
        left.push(sum);
    }
    // the n largest of the suffix, cut moving from 2 * n down to n
    var high = [];
    sum = 0;
    for (var j = 2 * n; j < 3 * n; j++) {
        heapPush(high, nums[j]);
        sum += nums[j];
    }
    var best = left[n] - sum;
    for (var k = 2 * n - 1; k >= n; k--) {
        heapPush(high, nums[k]);
        sum += nums[k] - heapPop(high); // evict the smallest
        best = Math.min(best, left[k - n] - sum);
    }
    return best;
};

var heapPush = function(h, v) {
    h.push(v);
    var i = h.length - 1;
    while (i > 0) {
        var p = (i - 1) >> 1;
        if (h[p] <= h[i]) break;
        var t = h[p]; h[p] = h[i]; h[i] = t;
        i = p;
    }
};

var heapPop = function(h) {
    var top = h[0];
    var last = h.pop();
    if (h.length > 0) {
        h[0] = last;
        var j = 0;
        for (;;) {
            var l = 2 * j + 1, r = l + 1, s = j;
            if (l < h.length && h[l] < h[s]) s = l;
            if (r < h.length && h[r] < h[s]) s = r;
            if (s === j) break;
            var t = h[s]; h[s] = h[j]; h[j] = t;
            j = s;
        }
    }
    return top;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming