leetcode

commit 38317d34b680f34a58fd599a3b858dd37deab83c
parent 24da96af079acc4401cf3fc3b19ea871e2458b54
Author: Jack Sangdahl <jack@pngu.org>
Date:   Thu, 17 Jul 2025 20:56:39 -0600

2163. minimum difference in sums after removal of elements

Diffstat:
A
min_diff_sum_remove_elem.py
 | 
51
+++++++++++++++++++++++++++++++++++++++++++++++++++

1 file changed, 51 insertions(+), 0 deletions(-)
diff --git a/min_diff_sum_remove_elem.py 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]))