Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

After removals, the first retained group must occur before the second. For a fixed boundary between them, minimizing their difference means choosing the smallest q values on the left and the largest q values on the right, where the original length is 3q. These choices are independent across that boundary.

Approach

Sweep forward with a max-heap retaining the smallest q values, recording their sum for each eligible prefix. Sweep backward with a min-heap retaining the largest q values, recording their sum for each eligible suffix. Once a heap contains q values, each additional insertion is followed by removal of the least useful value to restore its size. Try every boundary from after index q - 1 through after index 2q - 1, subtracting the best suffix sum from the best prefix sum. Return the minimum difference, which may be negative.

class Solution:
    def minimumDifference(self, nums: List[int]) -> int:
        n = len(nums)
        n3 = n // 3
        t1 = sum(nums[:n3])
        max_pq = [-x for x in nums[:n3]]
        heapq.heapify(max_pq)
        p1 = [0] * n
        p1[n3 - 1] = t1

        for i in range(n3, n3 * 2):
            t1 += nums[i]
            heapq.heappush(max_pq, -nums[i])
            t1 -= -heapq.heappop(max_pq)
            p1[i] = t1

        t2 = sum(nums[-n3:])
        min_pq = nums[-n3:]
        heapq.heapify(min_pq)
        p2 = [0] * n
        p2[n3 * 2] = t2

        for i in range(n3 * 2 - 1, n3 - 1, -1):
            t2 += nums[i]
            heapq.heappush(min_pq, nums[i])
            t2 -= heapq.heappop(min_pq)
            p2[i] = t2

        res = float('inf')

        for i in range(n3 - 1, n3 * 2):
            res = min(res, p1[i] - p2[i + 1])

        return res

Complexity analysis

Let N = nums.length and q = N / 3. Time is O(N log(q + 1)) for the two heap sweeps and boundary scan, including q = 1. Auxiliary space is O(N) for the heaps, prefix/suffix best-sum arrays and temporary slices. Python heapifies the initial q values; JavaScript builds each heap by insertion, within the same total bound.