Solution Explanation: Minimum Difference in Sums After Removal of Elements

This problem asks to find the minimum difference between the sums of two equal parts of an array after removing n elements. The solution uses a combination of heaps (priority queues) and prefix/suffix sums to efficiently achieve this.

Core Idea:

1. Removal of n elements: We need to strategically remove n elements to minimize the difference between the sums of the remaining two parts (each of size n).

2. Prefix and Suffix Sums: Instead of brute-forcing all possible combinations of removed elements, we use prefix sums to efficiently calculate the sum of the smallest n elements from the beginning of the array and suffix sums for the largest n elements from the end.

3. Heaps: To maintain the smallest n elements in the prefix and largest n elements in the suffix dynamically as we iterate, we use max-heap (q1) and min-heap (q2), respectively. This allows for efficient addition and removal of elements while tracking the sums.

4. Iteration and Minimization: We iterate through possible split points (where the array is divided into two parts of size n). For each split point i, we subtract the suffix sum (suf[i+1]) from the prefix sum (pre[i]) to get the difference. We track the minimum difference encountered.

Algorithm:

1. Initialization:

   • Calculate n (number of elements to remove).
   • Initialize pre and suf arrays to store prefix and suffix sums.
   • Initialize max-heap q1 and min-heap q2.

2. Prefix Sum Calculation:

   • Iterate from the beginning of the array up to 2n elements.
   • Add the current element to the running sum s.
   • Add the current element to the max-heap q1.
   • If q1 has more than n elements, remove the largest element (max-heap's top element) and update s.
   • Store the current s in pre[i].

3. Suffix Sum Calculation:

   • Iterate from the end of the array backward up to n+1 elements.
   • Add the current element to the running sum s.
   • Add the current element to the min-heap q2.
   • If q2 has more than n elements, remove the smallest element (min-heap's top element) and update s.
   • Store the current s in suf[i].

4. Minimization:

   • Iterate from n to 2n (possible split points).
   • Calculate the difference pre[i] - suf[i + 1] and update the minimum difference ans if necessary.

Time Complexity: O(N log N), dominated by heap operations.

Space Complexity: O(N) to store heaps and prefix/suffix sum arrays.

Code (Python):

import heapq
 
class Solution:
    def minimumDifference(self, nums: List[int]) -> int:
        m = len(nums)
        n = m // 3
 
        s = 0
        pre = [0] * (m + 1)
        q1 = []  # Max heap
        for i, x in enumerate(nums[: 2 * n], 1):
            s += x
            heapq.heappush(q1, -x)  # Negate for max heap
            if len(q1) > n:
                s -= -heapq.heappop(q1)
            pre[i] = s
 
        s = 0
        suf = [0] * (m + 1)
        q2 = []  # Min heap
        for i in range(m, n, -1):
            x = nums[i - 1]
            s += x
            heapq.heappush(q2, x)
            if len(q2) > n:
                s -= heapq.heappop(q2)
            suf[i] = s
 
        ans = float('inf')
        for i in range(n, 2 * n + 1):
            ans = min(ans, pre[i] - suf[i + 1])
        return ans
 

Similar implementations can be done in other languages like Java, C++, JavaScript, etc., using their respective priority queue implementations. The core logic remains the same.