[Leetcode] 2163. Minimum Difference in Sums After Removal of Elements

https://leetcode.com/problems/minimum-difference-in-sums-after-removal-of-elements/description/?envType=daily-question&envId=2025-07-18

initial

i really should spend more time thinking of initial idea cuz it wasnt that hard. I thought about heap but how do i store n number of elements in min and max heap?

I thought about when iterating through each num, if that num is bigger than current num in min heap, we add that to max index and vice versa. But that didnt work.

Then i saw solution (which was actully easy) of using prefix sum and diagram is helpful https://leetcode.com/problems/minimum-difference-in-sums-after-removal-of-elements/solutions/1747029/python-explanation-with-pictures-priority-queue/?envType=daily-question&envId=2025-07-18

We first do a forward pass from 0 until length -n, where n=length//3 cuz we wanna exclude the rightmost n elements. We calculate every possible min sum of n elements.

Note we cannot sum sum(min_heap[:n]) cuz heap doesn't guarantee the first n elements are the smallest n element. We should instead use a max heap that when its size is bigger than n, we pop that biggest element stored in the max heap and update cur_sum accordingly.

Same for backward pass.

sol

import heapq
from collections import deque
class Solution:
    def minimumDifference(self, nums: List[int]) -> int:
        min_heap=[]
        max_heap=[]
        length=len(nums)
        n=length//3
        min_sum,max_sum=[],deque()
        cur_sum=0
        for i in range(length - n):
            heapq.heappush(min_heap,-nums[i])
            cur_sum+=nums[i]
            if len(min_heap)>n:
                removed = -heapq.heappop(min_heap)
                cur_sum-=removed
            if len(min_heap)==n:
                min_sum.append(cur_sum)
        cur_sum=0
        ans=int(10e18)
        for i in range(length-1, n-1,-1):
            heapq.heappush(max_heap,nums[i])
            cur_sum+=nums[i]
            if len(max_heap)>n:
                removed=heapq.heappop(max_heap)
                cur_sum-=removed
            if len(max_heap)==n:
                max_sum.appendleft(cur_sum)
        print(min_heap)
        print(max_heap)
        for a,b in zip(min_sum,max_sum):
            ans=min(ans, a-b)
        return ans
            

complexity

n log n (log n cuz each heap operation is log n)
n space