2163. Minimum Difference in Sums After Removal of Elements

Difficulty: Hard

Topics:Array,Dynamic Programming,Heap (Priority Queue)

You are given a0-indexed integer arraynums consisting of3 * n elements.

You are allowed to remove anysubsequence of elements of sizeexactlyn fromnums. The remaining2 * n elements will be divided into twoequal parts:

• The firstn elements belonging to the first part and their sum issumfirst.
• The nextn elements belonging to the second part and their sum issumsecond.

Thedifference in sums of the two parts is denoted assumfirst - sumsecond.

• For example, ifsumfirst = 3 andsumsecond = 2, their difference is1.
• Similarly, ifsumfirst = 2 andsumsecond = 3, their difference is-1.

Returntheminimum difference possible between the sums of the two parts after the removal ofn 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 <= 105
• 1 <= nums[i] <= 105

Hint:

1. The lowest possible difference can be obtained when the sum of the first n elements in the resultant array is minimum, and the sum of the next n elements is maximum.
2. For every index i, think about how you can find the minimum possible sum of n elements with indices lesser or equal to i, if possible.
3. Similarly, for every index i, try to find the maximum possible sum of n elements with indices greater or equal to i, if possible.
4. Now for all indices, check if we can consider it as the partitioning index and hence find the answer.

Solution:

We need to find the minimum difference between the sums of two equal parts of an array after removing exactlyn elements from the original array of size3n. The remaining2n elements are divided into two parts: the firstn elements and the nextn elements. The difference is calculated as the sum of the first part minus the sum of the second part.

Approach

1. Problem Analysis: The problem requires us to remove anyn elements from the array such that the remaining elements are split into two parts of equal size. The goal is to minimize the difference between the sums of these two parts. The key insight is that the first part must consist of the smallestn elements from the left segment of the array, and the second part must consist of the largestn elements from the right segment. This ensures the difference(sum of first part - sum of second part) is minimized.

2. Intuition: For each possible split pointk (fromn to2n), we consider the left segment[0, k-1] and the right segment[k, 3n-1]. From the left segment, we select the smallestn elements to minimize their sum. From the right segment, we select the largestn elements to maximize their sum. The difference between these sums gives a candidate for the minimum difference. We evaluate all possible split points to find the overall minimum difference.

3. Algorithm Selection:

   • Left Segment Processing: Use a max-heap to keep track of the smallestn elements in the left segment. As we iterate fromn to2n, we add new elements to the heap and remove the largest element to maintain onlyn smallest elements.
   • Right Segment Processing: Use a min-heap to keep track of the largestn elements in the right segment. As we iterate from2n down ton, we add new elements to the heap and remove the smallest element to maintain onlyn largest elements.
   • Difference Calculation: For each split pointk, compute the difference between the sum of the left segment and the sum of the right segment. Track the minimum difference encountered.

4. Complexity Analysis:

   • Time Complexity: The algorithm processes each element once for both left and right segments, with heap operations takingO(log n) time per element. Thus, the overall time complexity isO(n log n).
   • Space Complexity: The algorithm uses two heaps of sizeO(n) and arrays to store intermediate sums, resulting inO(n) space complexity.

Let's implement this solution in PHP:2163. Minimum Difference in Sums After Removal of Elements

<?php/** * @param Integer[] $nums * @return Integer */functionminimumDifference($nums){........./**     * go to ./solution.php     */}// Test casesprintminimumDifference([3,1,2])."\n";// Output: -1printminimumDifference([7,9,5,8,1,3])."\n";// Output: 1?>

Explanation:

1. Initialization: The array size is3n. We initialize two arrays,left andright, to store sums of selected elements for possible split points.
2. Left Segment Processing:
   • Initial Setup: The firstn elements are added to a max-heap, and their sum is stored asleft[n].
   • Iteration: For each subsequent indexk fromn+1 to2n, add the current element to the heap, update the sum, and remove the largest element to maintainn smallest elements. Store the updated sum inleft[k].
3. Right Segment Processing:
   • Initial Setup: The lastn elements are added to a min-heap, and their sum is stored asright[2n].
   • Iteration: For each indexk from2n-1 down ton, add the current element to the heap, update the sum, and remove the smallest element to maintainn largest elements. Store the updated sum inright[k].
4. Difference Calculation: For each split pointk fromn to2n, compute the difference betweenleft[k] andright[k] and track the minimum difference encountered.
5. Result: The minimum difference found is returned as the solution.

This approach efficiently processes the array using heaps to maintain optimal elements for each segment, ensuring the solution is both optimal and computationally feasible.

Contact Links

If you found this series helpful, please consider giving therepository a star on GitHub or sharing the post on your favorite social networks 😍.Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

• LinkedIn
• GitHub