Minimum adjacent swaps to alternate parity

Array Greedy

42.2% acceptance

Feb 25, 2026

You are given an array nums of distinct integers. In one operation, you can swap any two adjacent elements in the array. An arrangement of the array is considered valid if the parity of adjacent elements alternates, meaning every pair of neighboring elements consists of one even and one odd number. Return the minimum number of adjacent swaps required to transform nums into any valid arrangement. If it is impossible to rearrange nums such that no two adjacent elements have the same parity, return -1.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_swaps(nums: Vec<i32>) -> i32 {
    let n = nums.len();
    let evens: Vec<usize> = (0..n).filter(|&i| nums[i] % 2 == 0).collect();
    let odds: Vec<usize> = (0..n).filter(|&i| nums[i] % 2 != 0).collect();
    let ne = evens.len();
    let no = odds.len();

    if ne.abs_diff(no) > 1 {
      return -1;
    }

    // Minimum swaps for a given target pattern:
    // Assign group A to slots 0,2,4,... (in relative order) and group B to 1,3,5,...
    // Count cross-group inversions: pairs (a, b) where a is from group A, b from group B,
    // a appears before b in original but A's target > B's target
    // (meaning b should come before a in the target arrangement).
    //
    // Equivalently: create a "target position" sequence.
    // A's elements get target positions: a_target[i] = 2*i (0-indexed in their group), mapped to 0,2,4,...
    // B's elements get target positions: b_target[j] = 2*j+1, mapped to 1,3,5,...
    // Then count inversions in the merged target sequence (relative to original order).

    let count_cross_inversions = |group_a: &[usize], group_b: &[usize]| -> i64 {
      // Build a sequence: for each element in original array order, record its "target position"
      // group_a[i] → target 2*i, group_b[j] → target 2*j+1
      let mut targets = vec![0usize; n];
      for (idx, &pos) in group_a.iter().enumerate() {
        targets[pos] = 2 * idx;
      }
      for (idx, &pos) in group_b.iter().enumerate() {
        targets[pos] = 2 * idx + 1;
      }
      // Count inversions in targets array using merge sort
      let mut arr: Vec<usize> = targets;
      merge_sort_inversions(&mut arr)
    };

    fn merge_sort_inversions(arr: &mut Vec<usize>) -> i64 {
      let n = arr.len();
      if n <= 1 { return 0; }
      let mid = n / 2;
      let mut left = arr[..mid].to_vec();
      let mut right = arr[mid..].to_vec();
      let mut inv = merge_sort_inversions(&mut left) + merge_sort_inversions(&mut right);
      let (mut i, mut j, mut k) = (0, 0, 0);
      while i < left.len() && j < right.len() {
        if left[i] <= right[j] {
          arr[k] = left[i]; i += 1;
        } else {
          inv += (left.len() - i) as i64;
          arr[k] = right[j]; j += 1;
        }
        k += 1;
      }
      while i < left.len() { arr[k] = left[i]; i += 1; k += 1; }
      while j < right.len() { arr[k] = right[j]; j += 1; k += 1; }
      inv
    }

    if ne == no {
      let c1 = count_cross_inversions(&evens, &odds); // even-first
      let c2 = count_cross_inversions(&odds, &evens); // odd-first
      c1.min(c2) as i32
    } else if ne > no {
      count_cross_inversions(&evens, &odds) as i32
    } else {
      count_cross_inversions(&odds, &evens) as i32
    }
  }
}