Minimum Difference in Sums After Removal of Elements

Quick Links

Problem Description

Ah, the classic dilemma of life: how to split your pizza evenly among friends without anyone feeling cheated. In the world of LeetCode, this translates to the problem of finding the minimum difference in sums after removing elements from an array. You have an array of integers, and you need to split it into three parts. But wait! You can only remove elements to achieve this perfect split. It’s like trying to divide a cake into three equal pieces while your friends are eyeing the biggest slice.

Imagine you have a bag of candies, and you want to share them with your two friends. But instead of just handing them out, you have to remove some candies first to make sure that the difference in the total number of candies each of you gets is as small as possible. Sounds fun, right?

Code Solution


import math
import heapq

class Solution:
    def minimumDifference(self, nums: list[int]) -> int:
        n = len(nums) // 3
        ans = math.inf
        leftSum = 0
        rightSum = 0
        maxHeap = []  # Left part, as small as possible
        minHeap = []  # Right part, as big as possible
        minLeftSum = [0] * len(nums)

        for i in range(2 * n):
            heapq.heappush(maxHeap, -nums[i])
            leftSum += nums[i]
            if len(maxHeap) == n + 1:
                leftSum += heapq.heappop(maxHeap)
            if len(maxHeap) == n:
                minLeftSum[i] = leftSum

        for i in range(len(nums) - 1, n - 1, -1):
            heapq.heappush(minHeap, nums[i])
            rightSum += nums[i]
            if len(minHeap) == n + 1:
                rightSum -= heapq.heappop(minHeap)
            if len(minHeap) == n:
                ans = min(ans, minLeftSum[i - 1] - rightSum)

        return ans

Approach Explanation

The approach taken in this solution is akin to a strategic game of balancing weights. We use heaps to keep track of the smallest and largest sums possible from the left and right parts of the array. The left part is managed with a max-heap (to keep the smallest elements) while the right part uses a min-heap (to keep the largest elements).

Left Part Calculation: We iterate through the first two-thirds of the array, maintaining a max-heap to ensure we can always get the smallest possible sum of n elements.
Right Part Calculation: We then iterate through the last third of the array, using a min-heap to keep track of the largest elements, allowing us to calculate the right sum efficiently.
Final Calculation: The minimum difference is computed by comparing the sums from both parts.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(N log N)
Space Complexity	O(N)

Real-World Example

Let’s say you’re at a party with 9 friends, and you have 9 different types of snacks. You want to divide them into three equal groups, but you can only remove some snacks. If you remove the snacks strategically, you can ensure that each group has a similar total weight of snacks. This is exactly what the problem is about—finding that perfect balance!