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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


    
    
    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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


    
    
    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

1
2
3
4
5
6
7
8
9


    
    
    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.length
  • 1 <= n <= 10^5
  • 1 <= 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

  1. Count the frequency of values where nums1[i] == nums2[i].
  2. Track the most frequent conflicting value and its count.
  3. Collect indices where nums1[i] != nums2[i] and neither value is the most frequent conflict.
  4. If the number of available indices is not enough to resolve all conflicts, return -1.
  5. Otherwise, select the smallest indices to swap and sum their costs.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#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;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

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 } }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

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 }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

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.