2163. Minimum Difference in Sums After Removal of Elements

HardArrayDynamic ProgrammingHeap (Priority Queue)
Leetcode Link

Problem Description

You are given an integer array nums with 3 * n elements. You are allowed to remove a subsequence of n elements from nums. After removing these n elements, you divide the remaining array into two equal parts, each containing n elements. The first part's sum is sum_first and the second part's sum is sum_second. Your goal is to minimize the absolute difference between these two sums.

In essence, you are trying to balance the sums of two subsequences by carefully choosing which n elements to remove to achieve the smallest possible difference between the sums of these two parts.

Intuition

To solve this problem, we need to use a strategy that allows us to calculate the sums of potential subarrays efficiently after removing a subsequence of elements. One way to approach the solution is to consider both the prefix sum and the suffix sum:

  1. Find max prefix sums for the first 2n elements: Starting from the left, we calculate the maximum sum of any n elements in the first 2n elements. We want to know the largest possible sum we could have on the left side when removing n elements.

  2. Find max suffix sums for the last 2n elements: Similarly, starting from the right, we calculate the maximum sum of any n elements in the last 2n elements. It gives us the same but for the right side, telling us the largest possible sum we could end up with on the right side, again after removing n elements.

  3. Use heaps to calculate these prefix and suffix sums: Since we are interested in the n largest sums at any point, we use a max heap for the prefix sum and a min heap for the suffix sum to keep track of the largest and smallest elements, respectively.

  4. Determine the minimum difference: We calculate the difference between the prefix sum and the suffix sum at every point possible (where the remaining 2n elements can be split into two equal parts after removing n elements). The smallest such difference would be our answer.

By breaking the problem into prefix and suffix calculations, we efficiently narrow down the sums we need to compare to determine the minimum possible difference.

Learn more about Dynamic Programming and Heap (Priority Queue) patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?

Solution Approach

The solution uses a two-heap approach and prefix/suffix sums to keep track of the potential maximum sum of n numbers in two segments of the array nums.

Here is a step-by-step breakdown of the solution approach:

  1. Initialization: Define two empty heaps, q1 for the prefix part and q2 for the suffix part. Also, create arrays pre and suf to store prefix and suffix sums respectively, each initialized with zeros and of size m + 1, where m is the length of the array nums.

  2. Prefix Sums Calculation:

    • Iterate through the first 2n elements of nums and push the negative of each element into heap q1 (max heap since Python's heapq is a min heap by default).
    • After each insertion, if the heap size exceeds n, remove the smallest element (which is the largest negative number) from the heap and adjust the running sum s.
    • Store the running sum s in pre at the current index to represent the maximum sum of n numbers for the first part up to that index.

  3. Suffix Sums Calculation:

    • Iterate through the last 2n elements of nums in reverse and push each element into heap q2 (min heap).
    • Similarly, if the heap size exceeds n, remove the smallest (top) element from the heap and adjust the running sum s.
    • Store the running sum s in suf at the current index to represent the maximum sum of n numbers for the second part starting at that index.

  4. Finding the Minimum Difference:

    • We can split nums into two parts after any index i in the range [n, 2n]. To achieve this, we calculate and compare pre[i] - suf[i + 1] for each i in this range.
    • The reason for the subtraction is that pre[i] stores the maximum sum of n numbers from the start to the ith index, whereas suf[i + 1] stores the maximum sum of n numbers from the i + 1th index to the end.
    • By comparing these values, we are effectively considering the best sums achievable for both parts of the array after removing a subsequence of n elements. This way, the minimum difference calculated represents the closest balance we can reach between the sums of the two parts, considering every possible split point within the range.

Throughout the implementation, heaps are utilized to keep track of the largest or smallest n elements in a running window, which allows us to efficiently calculate the desired maximum prefix and suffix sums. The approach makes sure that we consider every split point for the remaining 2n elements and thus guarantee that the minimum absolute difference is found.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How many times is a tree node visited in a depth first search?

Example Walkthrough

Let's say we have an integer array nums with 9 elements (n=3):

1nums = [1, 2, 3, 4, 5, 6, 7, 8, 9]

We can follow the solution approach outlined above:

  1. Initialization:

    • Create two empty heaps, q1 (as a max heap) and q2 (as a min heap).
    • Initialize the prefix sums array pre and the suffix sums array suf with zeros and of size 4 (3n + 1).
    1q1 = []
2q2 = []
3pre = [0, 0, 0, 0]
4suf = [0, 0, 0, 0]

  2. Prefix Sums Calculation:

    • Iterate through the first 6 elements (2n) of nums and push the negative of each element into q1.
    • If the heap q1 exceeds size 3, pop and subtract the smallest element (which is the largest negative number).
    • Update the pre array with the running sum s at each index.

  3. Suffix Sums Calculation:

    • Iterate through the last 6 elements (2n) of nums in reverse order and push each element into q2.
    • If the heap size q2 exceeds size 3, pop and subtract the smallest element.
    • Update the suf array with the running sum s at the corresponding index.

  4. Finding the Minimum Difference:

    • Calculate and compare pre[i] - suf[i + 1] for i ranging from 3 to 6.
    • The smallest difference is the answer.

Let's perform these calculations step by step with the example array:

Step 1: Prefix Sums

  • After iteration and maintaining the max heap: 
    1pre = [0, 1, 3, 6, 6, 10, 15]
  • We obtain the maximum sum of n numbers in the first 2n numbers of the array.

Step 2: Suffix Sums

  • Reverse iterating and maintaining the min heap: 
    1suf = [30, 23, 18, 14, 14, 9, 3, 0, 0, 0]
  • The suf array is filled similarly but in the reverse order from the end of the array.

Step 3: Calculate Minimum Difference

  • With our pre and suf arrays, we start comparing sums for the range [3, 6]:
1For i = 3: pre[i] = 6, suf[i + 1] = 14, difference = |6 - 14| = 8
2For i = 4: pre[i] = 6, suf[i + 1] = 9, difference = |6 - 9| = 3
3For i = 5: pre[i] = 10, suf[i + 1] = 3, difference = |10 - 3| = 7

The smallest difference is when i = 4 yielding an absolute difference of 3.

Therefore, to minimize the difference between sum_first and sum_second, we would remove three elements such that the remaining elements after index 4 and up to index 5 (inclusive) are balanced. This would give us:

1First part: [1, 2, 3, 4], sum_first = 10
2Second part: [6, 7, 8], sum_second = 21 - 12 (removed element at index 5) = 9

And the minimum absolute difference between the sums of these two parts is 3, as calculated.

Solution Implementation

1from heapq import heappush, heappop
2
3class Solution:
4    def minimumDifference(self, nums: List[int]) -> int:
5        total_elements = len(nums)
6        one_third_length = total_elements // 3  # Calculate the size of one-third of the array
7
8        prefix_sum = 0
9        max_heap_prefix = []  # Heap to keep track of the largest 'n' elements in the prefix
10        prefix_sums = [0] * (total_elements + 1)  # Initialize prefix sum array
11      
12        # Calculate prefix sums and maintain the heap with the largest 'n' elements
13        for i in range(1, one_third_length * 2 + 1):
14            prefix_sum += nums[i - 1]
15            heappush(max_heap_prefix, -nums[i - 1])  # Push the negation to use min-heap as max-heap
16            if len(max_heap_prefix) > one_third_length:
17                prefix_sum += heappop(max_heap_prefix)  # Pop the smallest (most negative) when heap size exceeds 'n'
18            prefix_sums[i] = prefix_sum
19      
20        suffix_sum = 0
21        min_heap_suffix = []  # Heap to keep track of the smallest 'n' elements in the suffix
22        suffix_sums = [0] * (total_elements + 1)  # Initialize suffix sum array
23      
24        # Calculate suffix sums and maintain the heap with the smallest 'n' elements
25        for i in range(total_elements, one_third_length - 1, -1):
26            suffix_sum += nums[i - 1]
27            heappush(min_heap_suffix, nums[i - 1])
28            if len(min_heap_suffix) > one_third_length:
29                suffix_sum -= heappop(min_heap_suffix)  # Pop the largest when heap size exceeds 'n'
30            suffix_sums[i] = suffix_sum
31      
32        # Find the minimum difference between the prefix and suffix sums
33        min_difference = float('inf')  # Start with an infinitely large difference
34        for i in range(one_third_length, one_third_length * 2 + 1):
35            min_difference = min(min_difference, prefix_sums[i] - suffix_sums[i + 1])  # Compare and store the minimum
36      
37        return min_difference
38
1class Solution {
2    public long minimumDifference(int[] nums) {
3        int totalLength = nums.length; // Total number of elements in nums.
4        int subsetSize = totalLength / 3; // Size of the subsets to be created.
5        long sum = 0; // Used to store the running sum.
6      
7        // Array to store the prefix sum for the first 2/3 of the array.
8        long[] prefixSums = new long[totalLength + 1];
9        // Initialize a max heap to find the largest elements in reverse order.
10        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
11        for (int i = 1; i <= subsetSize * 2; ++i) {
12            int element = nums[i - 1];
13            sum += element;
14            maxHeap.offer(element);
15            // If the max heap size exceeds the subset size, remove the largest element.
16            if (maxHeap.size() > subsetSize) {
17                sum -= maxHeap.poll();
18            }
19            // Store the running sum in prefixSums for the first 2/3 of the array.
20            prefixSums[i] = sum;
21        }
22      
23        sum = 0;
24        // Array to store the suffix sum for the last 2/3 of the array.
25        long[] suffixSums = new long[totalLength + 1];
26        // Initialize a min heap to find the smallest elements in order.
27        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
28        for (int i = totalLength; i > subsetSize; --i) {
29            int element = nums[i - 1];
30            sum += element;
31            minHeap.offer(element);
32            // If the min heap size exceeds the subset size, remove the smallest element.
33            if (minHeap.size() > subsetSize) {
34                sum -= minHeap.poll();
35            }
36            // Store the running sum in suffixSums for the last 2/3 of the array.
37            suffixSums[i] = sum;
38        }
39      
40        // Initialize answer with a very large value.
41        long answer = Long.MAX_VALUE;
42        // Go through the middle 1/3 of the array to find the minimum sum difference.
43        for (int i = subsetSize; i <= subsetSize * 2; ++i) {
44            answer = Math.min(answer, prefixSums[i] - suffixSums[i + 1]);
45        }
46        // Return the minimum sum difference.
47        return answer;
48    }
49}
50
1#include<vector>
2#include<queue> // Required for priority_queue
3
4using namespace std;
5
6class Solution {
7public:
8    long long minimumDifference(vector<int>& nums) {
9        int m = nums.size(); // Total number of elements in nums
10        int n = m / 3; // n is one third the size of the given array nums
11
12        using ll = long long; // Defined for ease of typing long long
13        ll sum = 0;
14      
15        // Array to track the prefix sum
16        ll prefixSum[m + 1]; // Sum of the largest `n` numbers up to the current index
17      
18        // Max heap for managing the largest elements
19        priority_queue<int> maxHeap;
20        // Calculate the prefix sums for the first `2n` elements
21        for (int i = 1; i <= n * 2; ++i) {
22            int element = nums[i - 1];
23            sum += element;
24            maxHeap.push(element);
25            // If the heap size exceeds n, pop the maximum element and subtract it from the sum
26            if (maxHeap.size() > n) {
27                sum -= maxHeap.top();
28                maxHeap.pop();
29            }
30            prefixSum[i] = sum;
31        }
32
33        sum = 0;
34        // Array to track the suffix sum
35        ll suffixSum[m + 1]; // Sum of the smallest `n` numbers starting from the current index
36
37        // Min heap for managing the smallest elements
38        priority_queue<int, vector<int>, greater<int>> minHeap;
39        // Calculate the suffix sums for the last `2n` elements
40        for (int i = m; i > n; --i) {
41            int element = nums[i - 1];
42            sum += element;
43            minHeap.push(element);
44            // If the heap size exceeds n, pop the minimum element and subtract it from the sum
45            if (minHeap.size() > n) {
46                sum -= minHeap.top();
47                minHeap.pop();
48            }
49            suffixSum[i] = sum;
50        }
51
52        // Initialize the answer with a large value
53        ll ans = 1e18;
54        // Loop through the middle third of nums, comparing prefix and suffix sums
55        for (int i = n; i <= n * 2; ++i) {
56            // Minimize the answer with the difference between prefix and suffix sums
57            ans = min(ans, prefixSum[i] - suffixSum[i + 1]);
58        }
59
60        // Return the minimum difference found
61        return ans;
62    }
63};
64
1import { MaxPriorityQueue, MinPriorityQueue } from 'typescript-collections';
2
3// Computes the minimum possible difference between the sum of any two non-overlapping thirds
4function minimumDifference(nums: number[]): number {
5    const totalLength = nums.length;           // Total length of the input array
6    const thirdLength = Math.floor(totalLength / 3);        // Length of one third of the array
7    let sum = 0;                              // Variable to keep the running sum
8    const prefixSums: number[] = Array(totalLength + 1);    // Array to store prefix sums
9    const maxQueue = new MaxPriorityQueue<number>();    // Max Priority Queue for managing the left side
10
11    // Compute prefix sums for the first two-thirds of the array
12    for (let i = 1; i <= thirdLength * 2; ++i) {
13        const element = nums[i - 1];
14        sum += element;
15        maxQueue.enqueue(element);
16        if (maxQueue.size() > thirdLength) {
17            sum -= maxQueue.dequeue().element;
18        }
19        prefixSums[i] = sum;
20    }
21
22    sum = 0;                                   // Resetting sum to compute suffix sums
23    const suffixSums: number[] = Array(totalLength + 1);    // Array to store suffix sums
24    const minQueue = new MinPriorityQueue<number>();    // Min Priority Queue for managing the right side
25
26    // Compute suffix sums for the last two-thirds of the array
27    for (let i = totalLength; i > thirdLength; --i) {
28        const element = nums[i - 1];
29        sum += element;
30        minQueue.enqueue(element);
31        if (minQueue.size() > thirdLength) {
32            sum -= minQueue.dequeue().element;
33        }
34        suffixSums[i] = sum;
35    }
36
37    let answer = Number.MAX_SAFE_INTEGER;      // Variable to store the minimum difference
38
39    // Find the minimum difference by comparing prefix and suffix sums
40    for (let i = thirdLength; i <= thirdLength * 2; ++i) {
41        answer = Math.min(answer, prefixSums[i] - suffixSums[i + 1]);
42    }
43
44    return answer;                             // Return the minimum difference
45}
46
Not Sure What to Study? Take the 2-min Quiz：

Which algorithm should you use to find a node that is close to the root of the tree?

Time and Space Complexity

The given Python code aims at finding the minimum possible difference between the sum of the elements of three equally-sized partitions of the array. It makes use of heaps to maintain the n-largest elements seen so far, where n = m / 3 and m is the length of the input list nums.

Time Complexity

The time complexity of the code is a result of several operations:

  1. Enumerating and processing the first 2/3 of the list: Each insertion into a heap (implemented as a priority queue) is O(log n), and we do this for the first 2n elements of the list, giving a total of O(2n log n) for this section.

  2. Iterating and processing the last 1/3 of the list backwards: Similarly, we apply a heap operation for each of the last n elements, resulting in O(n log n) time.

  3. Finding the minimum difference: This involves iterating through the middle third of the list to find the minimum difference. This is a linear operation with complexity O(n).

Therefore, the dominant term is the heap operations, summing up to a total time complexity of O(2n log n + n log n) which simplifies to O(m log(m/3)) since n = m / 3.

Space Complexity

The space complexity of the code is determined by:

  1. Heap storage: Two heaps are used, each storing up to n elements, thus requiring O(n) space.

  2. Precomputed sums: Two arrays, pre and suf, each of size m + 1, are used to store precomputed sums of heaps, contributing O(m) space.

  3. Variables and constants: A constant amount of additional space is used for variables and iteration, which does not depend on n or m and thus is O(1).

Considering the heaps and the arrays for precomputed sums, the total space complexity is O(m + 2n) which simplifies to O(m) since m is larger than 2n.

In conclusion, the given code has a time complexity of O(m log(m/3)) and a space complexity of O(m).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following is a good use case for backtracking?

Recommended Readings

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

Heap Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos heap svg Priority Queue and Heap What is the relationship between priority queue and heap Priority Queue is an Abstract Data Type and Heap is the concrete data structure we use to implement a priority queue Priority Queue A priority queue

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫