Minimum swaps to avoid forbidden values

Array Hash Table Greedy Counting

30.3% acceptance

Feb 25, 2026

109

You are given two integer arrays, nums and forbidden, each of length n. You may perform the following operation any number of times (including zero): Choose two distinct indices i and j, and swap nums[i] with nums[j]. Return the minimum number of swaps required such that, for every index i, the value of nums[i] is not equal to forbidden[i]. If no amount of swaps can ensure that every index avoids its forbidden value, return -1.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_swaps(nums: Vec<i32>, forbidden: Vec<i32>) -> i32 {
    let n = nums.len() as i32;
    // Count occurrences of each value in nums and in forbidden
    let mut num_cnt: std::collections::HashMap<i32, i32> = std::collections::HashMap::new();
    let mut forb_cnt: std::collections::HashMap<i32, i32> = std::collections::HashMap::new();
    for &v in &nums   { *num_cnt.entry(v).or_insert(0)  += 1; }
    for &v in &forbidden { *forb_cnt.entry(v).or_insert(0) += 1; }
    // Impossible: if count(v in nums) + count(v in forbidden) > n for any v,
    // there are more forbidden slots for v than non-v values available.
    for (&v, &fc) in &forb_cnt {
      let nc = *num_cnt.get(&v).unwrap_or(&0);
      if nc + fc > n { return -1; }
    }
    // Count bad positions (where nums[i] == forbidden[i])
    let bad: Vec<usize> = (0..n as usize).filter(|&i| nums[i] == forbidden[i]).collect();
    if bad.is_empty() { return 0; }
    let mut counts: std::collections::HashMap<i32, i32> = std::collections::HashMap::new();
    for &i in &bad { *counts.entry(nums[i]).or_insert(0) += 1; }
    let total = bad.len() as i32;
    let max_cnt = *counts.values().max().unwrap();
    // Pair up bad positions with different values (1 swap fixes 2);
    // excess same-valued bad positions each need 1 extra swap with a good position.
    if max_cnt > total / 2 { max_cnt } else { (total + 1) / 2 }
  }
}