Minimum Difference in Sums After Removal of Elements
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
nelements belong to the first part, and their sum issumfirst. - The next
nelements belong to the second part, and their sum issumsecond.
The difference in sums of the two parts is denoted as sumfirst - sumsecond.
- If
sumfirst = 3andsumsecond = 2, their difference is1. - If
sumfirst = 2andsumsecond = 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
-1Removing 3 leaves [1, 2], whose two parts have difference 1 - 2 = -1, which is the minimum possible.
Example 2
Input
nums = [7,9,5,8,1,3]Output
1Removing nums[1] = 9 and nums[4] = 1 leaves [7, 5, 8, 3], giving (7 + 5) - (8 + 3) = 1, and no smaller difference is possible.
Constraints
- nums.length == 3 * n
- 1 <= n <= 10^5
- 1 <= nums[i] <= 10^5