Skip to content

2163. Minimum Difference in Sums After Removal of Elements 👍

  • Time: $O(n\log n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
 public:
  long long minimumDifference(vector<int>& nums) {
    const int n = nums.size() / 3;
    long long ans = LLONG_MAX;
    long long leftSum = 0;
    long long rightSum = 0;
    // The left part should be as small as possible.
    priority_queue<int> maxHeap;
    // The right part should be as big as possible.
    priority_queue<int, vector<int>, greater<>> minHeap;
    // minLeftSum[i] := the minimum of the sum of n nums in nums[0..i)
    vector<long long> minLeftSum(nums.size());

    for (int i = 0; i < 2 * n; ++i) {
      maxHeap.push(nums[i]);
      leftSum += nums[i];
      if (maxHeap.size() == n + 1)
        leftSum -= maxHeap.top(), maxHeap.pop();
      if (maxHeap.size() == n)
        minLeftSum[i] = leftSum;
    }

    for (int i = nums.size() - 1; i >= n; --i) {
      minHeap.push(nums[i]);
      rightSum += nums[i];
      if (minHeap.size() == n + 1)
        rightSum -= minHeap.top(), minHeap.pop();
      if (minHeap.size() == n)
        ans = min(ans, minLeftSum[i - 1] - rightSum);
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
  public long minimumDifference(int[] nums) {
    final int n = nums.length / 3;
    long ans = Long.MAX_VALUE;
    long leftSum = 0;
    long rightSum = 0;
    // The left part should be as small as possible.
    Queue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
    // The right part should be as big as possible.
    Queue<Integer> minHeap = new PriorityQueue<>();
    // minLeftSum[i] := the minimum of the sum of n nums in nums[0..i)
    long[] minLeftSum = new long[nums.length];

    for (int i = 0; i < 2 * n; ++i) {
      maxHeap.offer(nums[i]);
      leftSum += nums[i];
      if (maxHeap.size() == n + 1)
        leftSum -= maxHeap.poll();
      if (maxHeap.size() == n)
        minLeftSum[i] = leftSum;
    }

    for (int i = nums.length - 1; i >= n; --i) {
      minHeap.offer(nums[i]);
      rightSum += nums[i];
      if (minHeap.size() == n + 1)
        rightSum -= minHeap.poll();
      if (minHeap.size() == n)
        ans = Math.min(ans, minLeftSum[i - 1] - rightSum);
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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[i] := the minimum of the sum of n nums in nums[0..i)
    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