Minimum total cost to make arrays unequal

Array Hash Table Greedy Counting

41.2% acceptance

Feb 25, 2026

234

You are given two 0-indexed integer arrays nums1 and nums2, of equal length n. In one operation, swap values at two indices of nums1 (cost = sum of those indices). Find minimum total cost such that nums1[i] != nums2[i] for all i. Strategy: indices where nums1[i]==nums2[i] MUST be included (cost += i). Track which value is "dominant" (appears most among the conflicting elements). If dominant count > total conflicting / 2, extend swaps until we get enough other values.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_total_cost(nums1: Vec<i32>, nums2: Vec<i32>) -> i64 {
    let n = nums1.len();
    let mut total_cost = 0i64;
    let mut swap_count = 0i64;
    let mut dominant_val = 0i32;
    let mut dominant_cnt = 0i64;
    let mut freq = vec![0i64; n + 1];

    for i in 0..n {
      if nums1[i] == nums2[i] {
        total_cost += i as i64;
        swap_count += 1;
        freq[nums1[i] as usize] += 1;
        if freq[nums1[i] as usize] > dominant_cnt {
          dominant_cnt = freq[nums1[i] as usize];
          dominant_val = nums1[i];
        }
      }
    }

    // If dominant value appears too many times, extend the swap set
    for i in 0..n {
      if dominant_cnt * 2 <= swap_count { break; }
      if nums1[i] == nums2[i] { continue; }
      if nums1[i] == dominant_val || nums2[i] == dominant_val { continue; }
      total_cost += i as i64;
      swap_count += 1;
    }

    if dominant_cnt * 2 > swap_count { -1 } else { total_cost }
  }
}