diff options
author | Jack Sangdahl <[email protected]> | 2025-07-17 20:56:39 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-07-17 20:56:39 -0600 |
commit | 38317d34b680f34a58fd599a3b858dd37deab83c (patch) | |
tree | f52b039f1a52a0be6e7c9da4213fcf7902682a57 | |
parent | 24da96af079acc4401cf3fc3b19ea871e2458b54 (diff) | |
download | leetcode-38317d34b680f34a58fd599a3b858dd37deab83c.tar.gz leetcode-38317d34b680f34a58fd599a3b858dd37deab83c.zip |
-rw-r--r-- | min_diff_sum_remove_elem.py | 51 |
1 files changed, 51 insertions, 0 deletions
diff --git a/min_diff_sum_remove_elem.py b/min_diff_sum_remove_elem.py new file mode 100644 index 0000000..40a6a18 --- /dev/null +++ b/min_diff_sum_remove_elem.py @@ -0,0 +1,51 @@ +# 2163. Minimum Difference in Sums After Removal of Elements +import heapq + +""" +you are given a 0-indexed integer array 'nums' consisting of '3 * n' +elements. you are allowed to remove any subsequence ofd 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', and 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'. return the minimum different possible +between the sums of the two parts after the removal of 'n' elements. +""" + + +class Solution(object): + def minimumDifference(self, nums): + """ + :type nums: List[int] + :rtype: int + """ + n = len(nums) // 3 + diff = [0] * (n + 1) + heapq.heapify(pq_l := [-i for i in nums[:n]]) + heapq.heapify(pq_r := nums[2 * n :]) + total = sum(nums[:n]) + ans = total + for i in range(n, 2 * n + 1): + diff[i - n] = total + curr = nums[i] + if curr >= -pq_l[0]: + continue + total += curr + pq_l[0] + heapq.heapreplace(pq_l, -curr) + total = sum(nums[2 * n :]) + ans -= total + for i in range(2 * n - 1, n - 2, -1): + diff[i - n + 1] -= total + ans = min(ans, diff[i - n + 1]) + curr = nums[i] + if curr <= pq_r[0]: + continue + total += curr - pq_r[0] + heapq.heapreplace(pq_r, curr) + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.minimumDifference(nums=[3, 1, 2])) + print(obj.minimumDifference(nums=[7, 9, 5, 8, 1, 3])) |