LeetCode 2163 - Minimum Difference in Sums After Removal of Elements

LeetCode Problem 2163

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Heap (Priority Queue)

Solution

Problem Understanding

The array contains exactly 3 * n elements. We must remove exactly n elements, leaving 2 * n elements behind. The remaining elements keep their original relative order because we are removing a subsequence, not rearranging the array.

After removal, the remaining 2 * n elements are split into two consecutive groups:

• The first n remaining elements contribute to sumfirst
• The next n remaining elements contribute to sumsecond

Our goal is to minimize:

$$sumfirst - sumsecond$$

This means we want the first half to be as small as possible and the second half to be as large as possible.

A very important observation is that the split between the two groups happens somewhere in the middle portion of the original array. The first group must come from the left side of the array, while the second group must come from the right side.

The constraints are large:

• n can be as large as 10^5
• Total array size can therefore reach 3 * 10^5

This immediately tells us that exponential or quadratic solutions are impossible. We need something close to O(n log n).

Another important detail is that all numbers are positive. This affects how we reason about minimizing and maximizing sums.

Several edge cases can easily break naive implementations:

• Very small arrays such as n = 1
• Arrays where all values are equal
• Strictly increasing or decreasing arrays
• Cases where the optimal removal involves elements from both the left and right portions
• Large values that can overflow 32-bit integers in some languages

The problem guarantees:

• The array length is always divisible by 3
• Every element is positive
• A valid removal always exists

Approaches

Brute Force Approach

A brute force solution would try every possible subsequence of size n to remove.

After removing those elements, we would:

1. Construct the remaining array
2. Split it into two equal halves
3. Compute the difference
4. Track the minimum result

This works because it exhaustively explores every valid removal.

However, the number of ways to choose n elements from 3n elements is:

$$\binom{3n}{n}$$

This grows exponentially and becomes completely infeasible even for moderate values of n.

For example, when n = 20, the number of possibilities is already enormous.

Key Insight

Instead of directly thinking about removed elements, it is easier to think about which elements remain.

Suppose we choose a split point i.

• The first group of n elements must be chosen from the prefix nums[0...i]
• The second group of n elements must be chosen from the suffix nums[i+1...]

To minimize:

$$sumfirst - sumsecond$$

we need:

• The minimum possible sum of n elements in the prefix
• The maximum possible sum of n elements in the suffix

This naturally suggests heap-based optimization.

We precompute:

• leftMin[i] = minimum possible sum of n elements chosen from nums[0...i]
• rightMax[i] = maximum possible sum of n elements chosen from nums[i...end]

Then every valid split can be evaluated in constant time:

$$leftMin[i] - rightMax[i+1]$$

The challenge becomes efficiently maintaining:

• The smallest n elements seen so far
• The largest n elements seen so far

Heaps are perfect for this.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Tries every removal subsequence
Optimal	O(n log n)	O(n)	Uses heaps to maintain optimal prefix and suffix sums

Algorithm Walkthrough

1. Let m = len(nums) and n = m // 3.

We will build two arrays:

• leftMin
• rightMax

2. Compute leftMin.

We scan from left to right while maintaining the smallest possible sum of exactly n elements.

We use a max heap because we want to keep the smallest n numbers.

The logic is:

• Add each number into the heap
• Add it to the running sum
• If heap size exceeds n, remove the largest element
• Once heap size becomes exactly n, record the sum

The heap always contains the smallest n values encountered so far. 3. Compute rightMax.

We scan from right to left while maintaining the largest possible sum of exactly n elements.

We use a min heap because we want to keep the largest n numbers.

The logic is:

• Add each number into the heap
• Add it to the running sum
• If heap size exceeds n, remove the smallest element
• Once heap size becomes exactly n, record the sum

The heap always contains the largest n values encountered so far. 4. Try every valid split point.

The first half must end somewhere between indices:

$$n - 1 \text{ through } 2n - 1$$

For each split:

• First half uses leftMin[i]
• Second half uses rightMax[i + 1]

Compute:

$$leftMin[i] - rightMax[i+1]$$

Track the minimum value. 5. Return the minimum difference.

Why it works

For every possible split position, the algorithm independently computes:

• The smallest achievable sum for the left side
• The largest achievable sum for the right side

Because these are optimal for that split, their difference is also optimal for that split. Evaluating all valid splits guarantees we find the globally minimum difference.

Python Solution

from typing import List
import heapq

class Solution:
    def minimumDifference(self, nums: List[int]) -> int:
        total_length = len(nums)
        n = total_length // 3

        left_min = [0] * total_length
        right_max = [0] * total_length

        # Compute minimum sums for prefixes
        max_heap = []
        current_sum = 0

        for i in range(total_length):
            value = nums[i]

            heapq.heappush(max_heap, -value)
            current_sum += value

            if len(max_heap) > n:
                removed = -heapq.heappop(max_heap)
                current_sum -= removed

            if len(max_heap) == n:
                left_min[i] = current_sum

        # Compute maximum sums for suffixes
        min_heap = []
        current_sum = 0

        for i in range(total_length - 1, -1, -1):
            value = nums[i]

            heapq.heappush(min_heap, value)
            current_sum += value

            if len(min_heap) > n:
                removed = heapq.heappop(min_heap)
                current_sum -= removed

            if len(min_heap) == n:
                right_max[i] = current_sum

        answer = float("inf")

        for i in range(n - 1, 2 * n):
            difference = left_min[i] - right_max[i + 1]
            answer = min(answer, difference)

        return answer

The implementation closely follows the algorithm described earlier.

The first loop computes left_min. The max heap is simulated in Python using negative values because Python's heapq only provides a min heap. At every step, the heap stores the smallest n values from the prefix.

The second loop computes right_max. Here we use a normal min heap. Whenever the heap exceeds size n, we remove the smallest value so that the heap always contains the largest n values from the suffix.

Finally, we iterate through all legal split positions and compute the difference between the best left sum and best right sum.

Go Solution

package main

import (
	"container/heap"
	"math"
)

type MaxHeap []int

func (h MaxHeap) Len() int {
	return len(h)
}

func (h MaxHeap) Less(i, j int) bool {
	return h[i] > h[j]
}

func (h MaxHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *MaxHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

func (h *MaxHeap) Pop() interface{} {
	old := *h
	n := len(old)
	value := old[n-1]
	*h = old[:n-1]
	return value
}

type MinHeap []int

func (h MinHeap) Len() int {
	return len(h)
}

func (h MinHeap) Less(i, j int) bool {
	return h[i] < h[j]
}

func (h MinHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *MinHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

func (h *MinHeap) Pop() interface{} {
	old := *h
	n := len(old)
	value := old[n-1]
	*h = old[:n-1]
	return value
}

func minimumDifference(nums []int) int64 {
	totalLength := len(nums)
	n := totalLength / 3

	leftMin := make([]int64, totalLength)
	rightMax := make([]int64, totalLength)

	maxHeap := &MaxHeap{}
	heap.Init(maxHeap)

	var currentSum int64 = 0

	for i := 0; i < totalLength; i++ {
		value := nums[i]

		heap.Push(maxHeap, value)
		currentSum += int64(value)

		if maxHeap.Len() > n {
			removed := heap.Pop(maxHeap).(int)
			currentSum -= int64(removed)
		}

		if maxHeap.Len() == n {
			leftMin[i] = currentSum
		}
	}

	minHeap := &MinHeap{}
	heap.Init(minHeap)

	currentSum = 0

	for i := totalLength - 1; i >= 0; i-- {
		value := nums[i]

		heap.Push(minHeap, value)
		currentSum += int64(value)

		if minHeap.Len() > n {
			removed := heap.Pop(minHeap).(int)
			currentSum -= int64(removed)
		}

		if minHeap.Len() == n {
			rightMax[i] = currentSum
		}
	}

	answer := int64(math.MaxInt64)

	for i := n - 1; i < 2*n; i++ {
		difference := leftMin[i] - rightMax[i+1]

		if difference < answer {
			answer = difference
		}
	}

	return answer
}

The Go implementation uses custom heap types because Go's container/heap package requires explicit interface implementations.

Unlike Python, Go does not support automatic big integers, so we use int64 for all sums and the final answer to avoid overflow.

The rest of the logic mirrors the Python solution exactly.

Worked Examples

Example 1

nums = [3,1,2]
n = 1

Step 1: Compute leftMin

Index	Value	Heap Contents	Sum	leftMin
0	3	[3]	3	3
1	1	[1]	1	1
2	2	[1]	1	1

Result:

leftMin = [3,1,1]

Step 2: Compute rightMax

Index	Value	Heap Contents	Sum	rightMax
2	2	[2]	2	2
1	1	[2]	2	2
0	3	[3]	3	3

Result:

rightMax = [3,2,2]

Step 3: Evaluate splits

Only valid split:

Split Index	leftMin[i]	rightMax[i+1]	Difference
0	3	2	1
1	1	2	-1

Minimum difference:

-1

Example 2

nums = [7,9,5,8,1,3]
n = 2

Step 1: Compute leftMin

Index	Heap Kept	Sum
1	[7,9]	16
2	[5,7]	12
3	[5,7]	12
4	[1,5]	6
5	[1,3]	4

Relevant values:

leftMin = [0,16,12,12,6,4]

Step 2: Compute rightMax

Index	Heap Kept	Sum
4	[1,3]	4
3	[8,3]	11
2	[8,5]	13
1	[9,8]	17
0	[9,8]	17

Relevant values:

rightMax = [17,17,13,11,4,0]

Step 3: Evaluate splits

Split Index	leftMin[i]	rightMax[i+1]	Difference
1	16	13	3
2	12	11	1
3	12	4	8

Minimum difference:

1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Each element is pushed and popped from a heap at most once
Space	O(n)	Heaps and auxiliary arrays store at most O(n) elements

The heaps never grow larger than n + 1, so each heap operation costs O(log n). Since we process all 3n elements twice, the total runtime is O(n log n).

The auxiliary arrays leftMin and rightMax each store 3n values, and both heaps store at most n values.

Test Cases

from typing import List

class Solution:
    def minimumDifference(self, nums: List[int]) -> int:
        import heapq

        total_length = len(nums)
        n = total_length // 3

        left_min = [0] * total_length
        right_max = [0] * total_length

        max_heap = []
        current_sum = 0

        for i in range(total_length):
            value = nums[i]

            heapq.heappush(max_heap, -value)
            current_sum += value

            if len(max_heap) > n:
                current_sum += heapq.heappop(max_heap)

            if len(max_heap) == n:
                left_min[i] = current_sum

        min_heap = []
        current_sum = 0

        for i in range(total_length - 1, -1, -1):
            value = nums[i]

            heapq.heappush(min_heap, value)
            current_sum += value

            if len(min_heap) > n:
                current_sum -= heapq.heappop(min_heap)

            if len(min_heap) == n:
                right_max[i] = current_sum

        answer = float("inf")

        for i in range(n - 1, 2 * n):
            answer = min(answer, left_min[i] - right_max[i + 1])

        return answer

solution = Solution()

assert solution.minimumDifference([3,1,2]) == -1  # smallest possible n
assert solution.minimumDifference([7,9,5,8,1,3]) == 1  # provided example
assert solution.minimumDifference([1,1,1]) == 0  # all equal values
assert solution.minimumDifference([1,2,3]) == -1  # increasing order
assert solution.minimumDifference([3,2,1]) == 1  # decreasing order
assert solution.minimumDifference([5,5,5,5,5,5]) == 0  # repeated values
assert solution.minimumDifference([10,1,1,1,1,10]) == -9  # strong imbalance
assert solution.minimumDifference([100000,100000,100000]) == 0  # large values
assert solution.minimumDifference([4,7,2,9,5,2]) == -5  # mixed values

Test	Why
[3,1,2]	Smallest valid input size
[7,9,5,8,1,3]	Official example
[1,1,1]	All elements equal
[1,2,3]	Strictly increasing array
[3,2,1]	Strictly decreasing array
[5,5,5,5,5,5]	Duplicate-heavy input
[10,1,1,1,1,10]	Optimal removal from both ends
[100000,100000,100000]	Large values and overflow safety
[4,7,2,9,5,2]	General mixed configuration

Edge Cases

One important edge case occurs when n = 1. In this situation, the array contains only three elements, and we remove exactly one. A buggy implementation may incorrectly handle split boundaries because there is only one valid element in each remaining half. The algorithm handles this naturally because the valid split range becomes very small, and the heap logic still works correctly.

Another important case is when all values are identical. In such arrays, every possible removal produces the same sums. Some greedy approaches accidentally rely on strict inequalities and can behave incorrectly with duplicates. Since the heap-based solution always maintains exactly n elements regardless of duplicates, it handles repeated values safely.

A third critical edge case is extremely large element values. Since each number can reach 10^5 and there can be up to 3 * 10^5 elements, sums can become very large. In Go, using standard int carelessly could overflow on some systems. The implementation therefore uses int64 for all sums and the final answer.

Another subtle case happens when the optimal removal uses elements from both the left and right sections of the array. A naive approach might incorrectly assume the removed elements form a contiguous block. The heap-based solution does not make this assumption because it evaluates all valid prefix and suffix combinations independently.