Minimize hamming distance after swap operations

Array Depth-First Search Union-Find

49.2% acceptance

Feb 25, 2026

896

You are given two integer arrays, source and target, both of length n. You are also given an array allowedSwaps where each allowedSwaps[i] = [ai, bi] indicates that you are allowed to swap the elements at index ai and index bi (0-indexed) of array source. The Hamming distance of two arrays of the same length, source and target, is the number of positions where the elements are different. Return the minimum Hamming distance of source and target after performing any amount of swap operations on array source.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

use std::collections::HashMap;

impl Solution {
  pub fn minimum_hamming_distance(source: Vec<i32>, target: Vec<i32>, allowed_swaps: Vec<Vec<i32>>) -> i32 {
    let n = source.len();
    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 swap in &allowed_swaps {
      let a = find(&mut parent, swap[0] as usize);
      let b = find(&mut parent, swap[1] as usize);
      if a != b { parent[a] = b; }
    }

    // Group indices by component
    let mut groups: HashMap<usize, Vec<usize>> = HashMap::new();
    for i in 0..n {
      let root = find(&mut parent, i);
      groups.entry(root).or_default().push(i);
    }

    let mut dist = 0;
    for indices in groups.values() {
      // Count source values in this group
      let mut src_count: HashMap<i32, i32> = HashMap::new();
      for &i in indices {
        *src_count.entry(source[i]).or_insert(0) += 1;
      }
      // For each target value, try to match
      for &i in indices {
        let t = target[i];
        if let Some(cnt) = src_count.get_mut(&t) {
          if *cnt > 0 { *cnt -= 1; continue; }
        }
        dist += 1;
      }
    }
    dist
  }
}