Minimum Total Cost to Make Arrays Unequal
HardUpdated: Aug 2, 2025
Practice on:
Problem
You are given two 0-indexed integer arrays nums1 and nums2, of equal length n.
In one operation, you can swap the values of any two indices of nums1. The
cost of this operation is the sum of the indices.
Find the minimum total cost of performing the given operation any number of times such that nums1[i] != nums2[i] for all 0 <= i <= n - 1
after performing all the operations.
Return _theminimum total cost such that _nums1 and nums2 satisfy the above condition. In case it is not possible, return -1.
Examples
Example 1
Input: nums1 = [1,2,3,4,5], nums2 = [1,2,3,4,5]
Output: 10
Explanation:
One of the ways we can perform the operations is:
- Swap values at indices 0 and 3, incurring cost = 0 + 3 = 3. Now, nums1 = [4,2,3,1,5]
- Swap values at indices 1 and 2, incurring cost = 1 + 2 = 3. Now, nums1 = [4,3,2,1,5].
- Swap values at indices 0 and 4, incurring cost = 0 + 4 = 4. Now, nums1 =[5,3,2,1,4].
We can see that for each index i, nums1[i] != nums2[i]. The cost required here is 10.
Note that there are other ways to swap values, but it can be proven that it is not possible to obtain a cost less than 10.
Example 2
Input: nums1 = [2,2,2,1,3], nums2 = [1,2,2,3,3]
Output: 10
Explanation:
One of the ways we can perform the operations is:
- Swap values at indices 2 and 3, incurring cost = 2 + 3 = 5. Now, nums1 = [2,2,1,2,3].
- Swap values at indices 1 and 4, incurring cost = 1 + 4 = 5. Now, nums1 = [2,3,1,2,2].
The total cost needed here is 10, which is the minimum possible.
Example 3
Input: nums1 = [1,2,2], nums2 = [1,2,2]
Output: -1
Explanation:
It can be shown that it is not possible to satisfy the given conditions irrespective of the number of operations we perform.
Hence, we return -1.
Constraints
n == nums1.length == nums2.length1 <= n <= 10^51 <= nums1[i], nums2[i] <= n
Solution
Method 1 – Greedy Counting and Swapping
Intuition
We need to ensure that for every index, nums1[i] != nums2[i]. The main challenge is when the same value appears at the same index in both arrays. We count the frequency of such conflicts and greedily swap with other indices to minimize cost, prioritizing swaps with the lowest indices.
Approach
- Count the frequency of values where
nums1[i] == nums2[i]. - Track the most frequent conflicting value and its count.
- Collect indices where
nums1[i] != nums2[i]and neither value is the most frequent conflict. - If the number of available indices is not enough to resolve all conflicts, return -1.
- Otherwise, select the smallest indices to swap and sum their costs.
Code
C++
#include <unordered_map>
class Solution {
public:
int minimumTotalCost(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size(), res = 0, maxFreq = 0, major = -1, cnt = 0;
unordered_map<int, int> freq;
vector<int> extra;
for (int i = 0; i < n; ++i) {
if (nums1[i] == nums2[i]) {
freq[nums1[i]]++;
if (freq[nums1[i]] > maxFreq) {
maxFreq = freq[nums1[i]];
major = nums1[i];
}
res += i;
} else {
extra.push_back(i);
}
}
int need = max(0, 2 * maxFreq - cnt);
for (int i : extra) {
if (need == 0) break;
if (nums1[i] != major && nums2[i] != major) {
res += i;
--need;
}
}
return need == 0 ? res : -1;
}
};
Go
func MinimumTotalCost(nums1, nums2 []int) int {
n := len(nums1)
freq := map[int]int{}
res, maxFreq, major := 0, 0, -1
extra := []int{}
for i := 0; i < n; i++ {
if nums1[i] == nums2[i] {
freq[nums1[i]]++
if freq[nums1[i]] > maxFreq {
maxFreq = freq[nums1[i]]
major = nums1[i]
}
res += i
} else {
extra = append(extra, i)
}
}
need := max(0, 2*maxFreq-len(extra))
for _, i := range extra {
if need == 0 {
break
}
if nums1[i] != major && nums2[i] != major {
res += i
need--
}
}
if need == 0 {
return res
}
return -1
}
func max(a, b int) int { if a > b { return a } else { return b } }
Java
class Solution {
public int minimumTotalCost(int[] nums1, int[] nums2) {
int n = nums1.length, res = 0, maxFreq = 0, major = -1, cnt = 0;
Map<Integer, Integer> freq = new HashMap<>();
List<Integer> extra = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (nums1[i] == nums2[i]) {
freq.put(nums1[i], freq.getOrDefault(nums1[i], 0) + 1);
if (freq.get(nums1[i]) > maxFreq) {
maxFreq = freq.get(nums1[i]);
major = nums1[i];
}
res += i;
cnt++;
} else {
extra.add(i);
}
}
int need = Math.max(0, 2 * maxFreq - cnt);
for (int i : extra) {
if (need == 0) break;
if (nums1[i] != major && nums2[i] != major) {
res += i;
need--;
}
}
return need == 0 ? res : -1;
}
}
Kotlin
class Solution {
fun minimumTotalCost(nums1: IntArray, nums2: IntArray): Int {
val n = nums1.size
var res = 0
var maxFreq = 0
var major = -1
var cnt = 0
val freq = mutableMapOf<Int, Int>()
val extra = mutableListOf<Int>()
for (i in 0 until n) {
if (nums1[i] == nums2[i]) {
freq[nums1[i]] = freq.getOrDefault(nums1[i], 0) + 1
if (freq[nums1[i]]!! > maxFreq) {
maxFreq = freq[nums1[i]]!!
major = nums1[i]
}
res += i
cnt++
} else {
extra.add(i)
}
}
var need = maxOf(0, 2 * maxFreq - cnt)
for (i in extra) {
if (need == 0) break
if (nums1[i] != major && nums2[i] != major) {
res += i
need--
}
}
return if (need == 0) res else -1
}
}
Python
from typing import List
from collections import Counter
class Solution:
def minimumTotalCost(self, nums1: List[int], nums2: List[int]) -> int:
n = len(nums1)
freq = Counter()
res, max_freq, major, cnt = 0, 0, -1, 0
extra = []
for i in range(n):
if nums1[i] == nums2[i]:
freq[nums1[i]] += 1
if freq[nums1[i]] > max_freq:
max_freq = freq[nums1[i]]
major = nums1[i]
res += i
cnt += 1
else:
extra.append(i)
need = max(0, 2 * max_freq - cnt)
for i in extra:
if need == 0:
break
if nums1[i] != major and nums2[i] != major:
res += i
need -= 1
return res if need == 0 else -1
Rust
use std::collections::HashMap;
impl Solution {
pub fn minimum_total_cost(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
let n = nums1.len();
let mut freq = HashMap::new();
let mut res = 0;
let mut max_freq = 0;
let mut major = -1;
let mut cnt = 0;
let mut extra = Vec::new();
for i in 0..n {
if nums1[i] == nums2[i] {
let e = freq.entry(nums1[i]).or_insert(0);
*e += 1;
if *e > max_freq {
max_freq = *e;
major = nums1[i];
}
res += i as i32;
cnt += 1;
} else {
extra.push(i);
}
}
let mut need = (2 * max_freq - cnt).max(0);
for &i in &extra {
if need == 0 { break; }
if nums1[i] != major && nums2[i] != major {
res += i as i32;
need -= 1;
}
}
if need == 0 { res } else { -1 }
}
}
TypeScript
class Solution {
minimumTotalCost(nums1: number[], nums2: number[]): number {
const n = nums1.length;
const freq = new Map<number, number>();
let res = 0, maxFreq = 0, major = -1, cnt = 0;
const extra: number[] = [];
for (let i = 0; i < n; i++) {
if (nums1[i] === nums2[i]) {
freq.set(nums1[i], (freq.get(nums1[i]) ?? 0) + 1);
if (freq.get(nums1[i])! > maxFreq) {
maxFreq = freq.get(nums1[i])!;
major = nums1[i];
}
res += i;
cnt++;
} else {
extra.push(i);
}
}
let need = Math.max(0, 2 * maxFreq - cnt);
for (const i of extra) {
if (need === 0) break;
if (nums1[i] !== major && nums2[i] !== major) {
res += i;
need--;
}
}
return need === 0 ? res : -1;
}
}
Complexity
- ⏰ Time complexity:
O(n)— We scan the arrays and count frequencies in linear time. - 🧺 Space complexity:
O(n)— For frequency maps and extra indices.