Maximize alternating sum using swaps

Array Greedy Union-Find Sorting

64.1% acceptance

Feb 25, 2026

You are given an integer array nums. You want to maximize the alternating sum of nums, which is defined as the value obtained by adding elements at even indices and subtracting elements at odd indices. That is, nums[0] - nums[1] + nums[2] - nums[3]... You are also given a 2D integer array swaps where swaps[i] = [pi, qi]. For each pair [pi, qi] in swaps, you are allowed to swap the elements at indices pi and qi. These swaps can be performed any number of times and in any order. Return the maximum possible alternating sum of nums.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_alternating_sum(nums: Vec<i32>, swaps: Vec<Vec<i32>>) -> i64 {
    let n = nums.len();
    // Union-Find: indices in the same component can be freely rearranged.
    let mut parent: Vec<usize> = (0..n).collect();
    fn find(parent: &mut Vec<usize>, x: usize) -> usize {
      if parent[x] != x { parent[x] = find(parent, parent[x]); }
      parent[x]
    }
    for s in &swaps {
      let a = s[0] as usize;
      let b = s[1] as usize;
      let pa = find(&mut parent, a);
      let pb = find(&mut parent, b);
      if pa != pb { parent[pa] = pb; }
    }
    // For each component, collect its indices and values.
    // Then optimally assign: put large values at even positions, small at odd.
    use std::collections::HashMap;
    let mut components: HashMap<usize, (Vec<usize>, Vec<i32>)> = HashMap::new();
    for i in 0..n {
      let p = find(&mut parent, i);
      let e = components.entry(p).or_default();
      e.0.push(i);
      e.1.push(nums[i]);
    }
    let mut total = 0i64;
    for (_, (indices, mut vals)) in components {
      let even_count = indices.iter().filter(|&&i| i % 2 == 0).count();
      let _odd_count = indices.len() - even_count;
      // Sort values descending
      vals.sort_unstable_by(|a, b| b.cmp(a));
      // Assign top even_count to even positions (add), rest to odd (subtract)
      let mut sum = 0i64;
      for (idx, &v) in vals.iter().enumerate() {
        if idx < even_count {
          sum += v as i64; // at even position: add
        } else {
          sum -= v as i64; // at odd position: subtract
        }
      }
      total += sum;
    }
    total
  }
}