aboutsummaryrefslogtreecommitdiff
path: root/min_diff_sum_remove_elem.py
blob: 40a6a18614e71cbb206aec3daad3de130c484a5f (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
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]))