Minimum Difference in Sums After Removal of Elements

HARD

Description

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

Checkout 2 different approaches to solve Minimum Difference in Sums After Removal of Elements. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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.

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;
    }
}

Complexity Analysis

Time Complexity: 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 Complexity: O(n), for storing the prefix and suffix subarrays in each iteration. The size of these subarrays can be up to `2n`.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Minimum Difference in Sums After Removal of Elements. Click on different languages to view the code.

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;
  }
}

Video Solution

Watch the video walkthrough for Minimum Difference in Sums After Removal of Elements

Patterns:

Dynamic Programming

Data Structures:

ArrayHeap (Priority Queue)