Minimum difference in sums after removal of elements

Array Dynamic Programming Heap (Priority Queue)

69.8% acceptance

Feb 25, 2026

1134

You are given a 0-indexed integer array nums consisting of 3 * n elements. Remove any subsequence of exactly n elements. The remaining 2*n elements are split into two equal parts: first n elements (sumfirst) and next n elements (sumsecond). Return the minimum difference possible: sumfirst - sumsecond.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_difference(nums: Vec<i32>) -> i64 {
    use std::collections::BinaryHeap;
    use std::cmp::Reverse;

    let m = nums.len();
    let n = m / 3;

    // prefix_min[i] = min sum of n elements from nums[0..=i], for i >= n-1
    let mut prefix_min = vec![0i64; m];
    let mut max_heap: BinaryHeap<i32> = BinaryHeap::new();
    let mut cur = 0i64;
    for i in 0..m {
      max_heap.push(nums[i]);
      cur += nums[i] as i64;
      if max_heap.len() > n {
        cur -= max_heap.pop().unwrap() as i64;
      }
      if i >= n - 1 {
        prefix_min[i] = cur;
      }
    }

    // suffix_max[i] = max sum of n elements from nums[i..], for i <= 2*n
    let mut suffix_max = vec![0i64; m + 1];
    let mut min_heap: BinaryHeap<Reverse<i32>> = BinaryHeap::new();
    let mut cur2 = 0i64;
    for i in (0..m).rev() {
      min_heap.push(Reverse(nums[i]));
      cur2 += nums[i] as i64;
      if min_heap.len() > n {
        cur2 -= min_heap.pop().unwrap().0 as i64;
      }
      if i <= 2 * n {
        suffix_max[i] = cur2;
      }
    }

    // Min of prefix_min[k] - suffix_max[k+1] for k in n-1..=2n-1
    (n - 1..=2 * n - 1)
      .map(|k| prefix_min[k] - suffix_max[k + 1])
      .min()
      .unwrap()
  }
}