Problem Statement

LeetCode 2163: Minimum Difference in Sums After Removal of Elements
Difficulty: Hard
Topics: Array, Dynamic Programming, Heap (Priority Queue)
Date: 18 July 2025

You are given a 0-indexed integer array nums consisting of 3 * n elements. You are allowed to remove any subsequence of 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 sumfirst
The next n elements belonging to the second part and their sum is sumsecond

The difference in sums of the two parts is denoted as sumfirst - sumsecond.

Return the minimum difference possible between the sums of the two parts after the removal of n elements.

Examples

Example 1:

Input: nums = [3,1,2]
Output: -1
Explanation: n = 1, so we remove 1 element and split into two parts of 1 element each.
- Remove 3: [1,2] → 1 - 2 = -1
- Remove 1: [3,2] → 3 - 2 = 1  
- Remove 2: [3,1] → 3 - 1 = 2
Minimum difference = -1

Example 2:

Input: nums = [7,9,5,8,1,3]
Output: 1
Explanation: n = 2, so we remove 2 elements and split into two parts of 2 elements each.
Optimal: Remove 9 and 1 → [7,5,8,3] → (7+5) - (8+3) = 1

Constraints

nums.length == 3 * n
1 <= n <= 10^5
1 <= nums[i] <= 10^5

Algorithm Walkthrough

Key Insight

To minimize sumfirst - sumsecond, we want:

sumfirst to be as small as possible
sumsecond to be as large as possible

The crucial observation is that after removing n elements, the remaining 2n elements maintain their relative positions. We can think of this as choosing a "split point" where:

The first part takes the n smallest available elements from the left portion
The second part takes the n largest available elements from the right portion

Strategy

Precompute left minimums: For each position i, calculate the minimum possible sum of n elements from nums[0...i]
Precompute right maximums: For each position i, calculate the maximum possible sum of n elements from nums[i...3n-1]
Find optimal split: Try all valid split points and find the minimum difference

Step-by-Step Implementation

Step 1: Build Left Minimums Array

We use a max heap to maintain the n smallest elements seen so far:

// leftMins[i] = minimum sum of n elements from nums[0...i]
for (int i = 0; i < 2 * n; i++) {
    maxHeap.offer(nums[i]);
    sum += nums[i];

    if (maxHeap.size() > n) {
        sum -= maxHeap.poll();  // Remove largest element
    }

    if (maxHeap.size() == n) {
        leftMins[i] = sum;
    }
}

Why max heap? We want to keep the n smallest elements. When we encounter a new element smaller than our current largest small element, we replace the largest.

Step 2: Build Right Maximums Array

We use a min heap to maintain the n largest elements, processing from right to left:

// rightMaxs[i] = maximum sum of n elements from nums[i...3n-1]
for (int i = 3*n - 1; i >= n; i--) {
    minHeap.offer(nums[i]);
    sum += nums[i];

    if (minHeap.size() > n) {
        sum -= minHeap.poll();  // Remove smallest element
    }

    if (minHeap.size() == n) {
        rightMaxs[i] = sum;
    }
}

Why min heap? We want to keep the n largest elements. When we encounter a new element larger than our current smallest large element, we replace the smallest.

Step 3: Find Minimum Difference

long result = Long.MAX_VALUE;
for (int i = n - 1; i < 2 * n; i++) {
    result = Math.min(result, leftMins[i] - rightMaxs[i + 1]);
}

Complete Solution

class Solution {
    public long minimumDifference(int[] nums) {
        int n = nums.length / 3;

        long[] leftMins = new long[nums.length];
        long[] rightMaxs = new long[nums.length];

        // Build leftMins: minimum sum of n elements from left
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a,b) -> b-a);
        long sum = 0;

        for (int i = 0; i < 2 * n; i++) {
            maxHeap.offer(nums[i]);
            sum += nums[i];

            if (maxHeap.size() > n) {
                sum -= maxHeap.poll();
            }

            if (maxHeap.size() == n) {
                leftMins[i] = sum;
            }
        }

        // Build rightMaxs: maximum sum of n elements from right
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        sum = 0;

        for (int i = nums.length - 1; i >= n; i--) {
            minHeap.offer(nums[i]);
            sum += nums[i];

            if (minHeap.size() > n) {
                sum -= minHeap.poll();
            }

            if (minHeap.size() == n) {
                rightMaxs[i] = sum;
            }
        }

        // Find minimum difference
        long result = Long.MAX_VALUE;
        for (int i = n - 1; i < 2 * n; i++) {
            result = Math.min(result, leftMins[i] - rightMaxs[i + 1]);
        }

        return result;
    }
}

Example Trace

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

Building leftMins:

i=0: heap=[7], sum=7
i=1: heap=[9,7], sum=16, leftMins[1]=16
i=2: heap=[7,5], sum=12, leftMins[2]=12 (replaced 9 with 5)
i=3: heap=[7,5], sum=12, leftMins[3]=12 (8 > 7, no change)

Building rightMaxs:

i=5: heap=[3], sum=3
i=4: heap=[3,1], sum=4, rightMaxs[4]=4
i=3: heap=[8,3], sum=11, rightMaxs[3]=11 (replaced 1 with 8)
i=2: heap=[8,5], sum=13, rightMaxs[2]=13 (replaced 3 with 5)

Finding minimum difference:

i=1: leftMins[1] - rightMaxs[2] = 16 - 13 = 3
i=2: leftMins[2] - rightMaxs[3] = 12 - 11 = 1
i=3: leftMins[3] - rightMaxs[4] = 12 - 4 = 8

Result: 1

Complexity Analysis

Time Complexity: O(n log n)

Breakdown:

Building leftMins: O(n log n)
- Loop runs for 2n iterations
- Each heap operation (offer/poll) takes O(log n)
- Total: O(2n × log n) = O(n log n)
Building rightMaxs: O(n log n)
- Loop runs for 2n iterations
- Each heap operation takes O(log n)
- Total: O(2n × log n) = O(n log n)
Finding minimum: O(n)
- Single loop through n elements
- Constant time operations inside

Overall: O(n log n) + O(n log n) + O(n) = O(n log n)

Space Complexity: O(n)