3868. Minimum Cost to Equalize Arrays Using Swaps

MediumGreedyArrayHash TableCounting

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given two integer arrays nums1 and nums2, each of size n.

You are allowed to perform the following two operations, any number of times, on these arrays:

Swap within the same array: Pick two indices i and j. Then choose to swap either nums1[i] with nums1[j], or nums2[i] with nums2[j]. This operation is free (costs nothing).
Swap between the two arrays: Pick an index i. Then swap nums1[i] with nums2[i]. This operation costs 1.

Your goal is to make nums1 and nums2 identical (the same array). Return the minimum cost required to achieve this. If it is impossible to make them identical, return -1.

In other words, you can freely rearrange the elements within each array, but moving an element from one array to the other (at the same position) costs 1. You need to find the cheapest way to make the two arrays equal, considering that the free swaps let you reorder elements however you like within each array.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Hash Table / Counting?

This problem maps to Hash Table / Counting through a short path in the full flowchart.

Count surpluses via hash maps, cancel matches between arrays, then verify even parity and sum half-counts.

Open in Flowchart

Intuition

Since we can freely reorder the elements within each array, the positions of the elements don't matter at all. What truly matters is the multiset of values in nums1 and the multiset of values in nums2. The free swaps let us arrange any element to any position we want, so the only thing we cannot do for free is move a value from one array to the other.

For the two arrays to become identical, both arrays must end up with exactly the same collection of values. Think about the total pool of all numbers across both arrays. For the final arrays to match, each distinct value must appear an even number of times in total — because that total must be split evenly, half going to nums1 and half going to nums2. If any value appears an odd number of times overall, it's impossible to balance, so we return -1.

Now consider how many elements actually need to move between the arrays. If a value x already appears in both arrays, we can pair those occurrences up and leave them where they are — no cost. The problem only arises with the leftover elements that exist in one array but have no match in the other. These leftovers are exactly the ones we need to fix using the costly cross-array swap.

This leads to a counting idea:

We count occurrences of each value. Whenever a value in nums1 finds a matching occurrence in nums2, we cancel them out, since these pairs are already satisfied.
After cancellation, cnt1 holds the leftover values from nums1, and cnt2 holds the leftover values from nums2.
For each leftover value, its count must be even. If it's odd, balancing is impossible, so we return -1.

Why does the cost come from cnt1 alone? Each cross-array swap at an index exchanges one element of nums1 with one element of nums2. So a single paid swap fixes two mismatched slots at once — it pushes an unwanted value out of nums1 while pulling a needed value in. For every two extra copies of a value sitting in nums1, one swap is enough to move one of them over. Summing v // 2 over all leftover counts in cnt1 therefore gives the minimum number of paid swaps, which is our answer.

Pattern Learn more about Greedy patterns.

Solution Approach

Solution 1: Hash Table

We use two hash tables, cnt1 and cnt2, to track the leftover (unmatched) values from each array. The key idea is to cancel out matches during counting, so that what remains is exactly the set of elements that still need to be balanced.

Step 1: Count nums2 first.

We build cnt2 as a Counter of all values in nums2. This gives us a ready supply of values that nums1 can match against.

cnt2 = Counter(nums2)

Step 2: Walk through nums1 and cancel matches on the fly.

We initialize an empty counter cnt1. For each value x in nums1:

If cnt2[x] is still positive, it means nums2 has a spare copy of x. We pair them up by decrementing cnt2[x]. No leftover is recorded — this pair is already satisfied for free.
Otherwise, x has no partner in nums2, so it becomes a leftover and we increment cnt1[x].

cnt1 = Counter()
for x in nums1:
    if cnt2[x]:
        cnt2[x] -= 1
    else:
        cnt1[x] += 1

After this loop, cnt1 holds the leftover values originating from nums1, and cnt2 holds the leftover values originating from nums2.

Step 3: Check feasibility and accumulate the cost.

We iterate over the counts in cnt1. For each count v:

If v is odd, the value cannot be split evenly between the two arrays, so the task is impossible and we return -1.
Otherwise, each paid swap handles two extra copies, so this value contributes v // 2 swaps to the answer.

ans = 0
for v in cnt1.values():
    if v % 2 == 1:
        return -1
    ans += v // 2

Step 4: Verify cnt2 is also balanced.

By the same logic, every leftover count in cnt2 must be even. If any is odd, we return -1. We don't add to ans here, because the swaps counted from cnt1 already account for moving values across both directions — each swap simultaneously fixes one slot in nums1 and one in nums2.

for v in cnt2.values():
    if v % 2 == 1:
        return -1
return ans

Complexity Analysis:

Time complexity: O(n), where n is the length of the arrays. We make a constant number of passes over the data and the hash table operations are O(1) on average.
Space complexity: O(n), for storing the counts of values in the two hash tables.

Example Walkthrough

Let's trace through the solution with a small example:

nums1 = [4, 2, 2, 2]
nums2 = [1, 4, 1, 2]
n = 4

Our goal is to make both arrays hold the same multiset of values, paying 1 for each cross-array swap (swapping nums1[i] with nums2[i]), while reordering within each array is free.

Step 1: Count nums2 first.

We build cnt2 from all values in nums2:

cnt2 = {1: 2, 4: 1, 2: 1}

This is our supply of values that nums1 can try to match against.

Step 2: Walk through nums1 and cancel matches on the fly.

Start with cnt1 = {}. Process each value x in nums1 = [4, 2, 2, 2]:

`x`	`cnt2[x]` before	Match?	Action	`cnt1` after	`cnt2` after
`4`	`1`	Yes	decrement `cnt2[4]`	`{}`	`{1:2, 4:0, 2:1}`
`2`	`1`	Yes	decrement `cnt2[2]`	`{}`	`{1:2, 4:0, 2:0}`
`2`	`0`	No	increment `cnt1[2]`	`{2:1}`	`{1:2, 4:0, 2:0}`
`2`	`0`	No	increment `cnt1[2]`	`{2:2}`	`{1:2, 4:0, 2:0}`

After the loop:

cnt1 = {2: 2}        # leftover values stuck in nums1
cnt2 = {1: 2}        # leftover values stuck in nums2 (zeros ignored)

Intuitively: the 4 and one 2 were already shared by both arrays, so they're satisfied for free. What remains unbalanced is two extra 2s in nums1 and two extra 1s in nums2.

Step 3: Check feasibility and accumulate the cost from cnt1.

Iterate over cnt1.values():

Value 2 has count 2 → even ✓, contributes 2 // 2 = 1 swap.

So ans = 1.

Step 4: Verify cnt2 is also balanced.

Iterate over cnt2.values():

Value 1 has count 2 → even ✓, no -1 triggered.

We don't add to ans here — the single swap already fixes both sides at once.

Result: 1.

To see why one swap suffices, perform a cross-array swap at the index holding an extra 2 in nums1 and a 1 in nums2. That single paid swap pushes a surplus 2 out of nums1 and pulls in a needed 1, simultaneously repairing the surplus 1 in nums2. After this one swap, free in-array reordering makes both arrays identical — giving a minimum cost of 1.

Solution Implementation

1from collections import Counter
2
3
4class Solution:
5    def minCost(self, nums1: list[int], nums2: list[int]) -> int:
6        # Count occurrences of each value in nums2.
7        count2 = Counter(nums2)
8        # Will hold the surplus values from nums1 that cannot be
9        # directly matched against nums2.
10        count1 = Counter()
11
12        # Walk through nums1 and try to cancel each value with one
13        # available occurrence in nums2. Anything left over is a surplus.
14        for value in nums1:
15            if count2[value]:
16                count2[value] -= 1
17            else:
18                count1[value] += 1
19
20        swaps = 0
21
22        # Surplus values in nums1 must appear an even number of times so
23        # they can be paired up (each pair resolved with one swap).
24        for freq in count1.values():
25            if freq % 2 == 1:
26                return -1
27            swaps += freq // 2
28
29        # Remaining values in nums2 must also have even frequencies,
30        # otherwise the arrays cannot be balanced.
31        for freq in count2.values():
32            if freq % 2 == 1:
33                return -1
34
35        return swaps
36

1class Solution {
2    public int minCost(int[] nums1, int[] nums2) {
3        // Count the occurrences of each value in nums2.
4        Map<Integer, Integer> remainingInNums2 = new HashMap<>();
5        for (int value : nums2) {
6            remainingInNums2.merge(value, 1, Integer::sum);
7        }
8
9        // Track values from nums1 that conflict (same value occupies the same index pairing).
10        Map<Integer, Integer> conflictCount = new HashMap<>();
11        for (int value : nums1) {
12            int available = remainingInNums2.getOrDefault(value, 0);
13            if (available > 0) {
14                // This value can be matched/consumed from nums2's pool.
15                remainingInNums2.put(value, available - 1);
16            } else {
17                // No match available, so this value becomes a conflict to resolve.
18                conflictCount.merge(value, 1, Integer::sum);
19            }
20        }
21
22        int answer = 0;
23
24        // Each conflicting value must appear an even number of times to be paired.
25        for (int count : conflictCount.values()) {
26            if ((count & 1) == 1) {
27                // An odd count cannot be paired, making the task impossible.
28                return -1;
29            }
30            // Every pair of identical conflicts requires one swap.
31            answer += count / 2;
32        }
33
34        // The leftover values in nums2 must also be evenly distributable.
35        for (int count : remainingInNums2.values()) {
36            if ((count & 1) == 1) {
37                return -1;
38            }
39        }
40
41        return answer;
42    }
43}
44

1class Solution {
2public:
3    int minCost(vector<int>& nums1, vector<int>& nums2) {
4        // Count occurrences of each value in nums2.
5        unordered_map<int, int> count2;
6        for (int value : nums2) {
7            ++count2[value];
8        }
9
10        // For each value in nums1, cancel it against a matching value in nums2.
11        // Whatever cannot be matched is recorded as a "leftover" in count1.
12        unordered_map<int, int> count1;
13        for (int value : nums1) {
14            if (count2[value] > 0) {
15                // This value is already paired between the two arrays, no action needed.
16                --count2[value];
17            } else {
18                // Unmatched value from nums1.
19                ++count1[value];
20            }
21        }
22
23        int ans = 0;
24
25        // Process leftover values from nums1.
26        // Each leftover value must occur an even number of times so it can be split evenly;
27        // otherwise the arrays can never be made equal.
28        for (auto& [value, freq] : count1) {
29            if (freq & 1) {
30                return -1; // Odd count means it is impossible.
31            }
32            ans += freq / 2; // Each pair requires one swap.
33        }
34
35        // Process leftover values from nums2.
36        // These must also occur an even number of times for a valid arrangement.
37        for (auto& [value, freq] : count2) {
38            if (freq & 1) {
39                return -1; // Odd count means it is impossible.
40            }
41        }
42
43        return ans;
44    }
45};
46

1/**
2 * Computes the minimum cost to satisfy the pairing condition between nums1 and nums2.
3 * Returns -1 if the arrangement is impossible (any leftover group has odd count).
4 *
5 * Approach:
6 * 1. Tally how many times each value appears in nums2.
7 * 2. Walk through nums1; for each value try to "cancel" it against an
8 *    available occurrence in nums2. Values in nums1 that cannot be cancelled
9 *    are accumulated into cnt1.
10 * 3. Every leftover group must contain an even number of items so that they
11 *    can be paired (swapped). The cost contributed by a group of size v is
12 *    floor(v / 2). If any group is odd, the task is impossible.
13 *
14 * @param nums1 - first input array
15 * @param nums2 - second input array
16 * @returns the minimum cost, or -1 when impossible
17 */
18function minCost(nums1: number[], nums2: number[]): number {
19    // Frequency map for every value contained in nums2.
20    const countInNums2 = new Map<number, number>();
21
22    for (const value of nums2) {
23        countInNums2.set(value, (countInNums2.get(value) ?? 0) + 1);
24    }
25
26    // Frequency map for the values in nums1 that could not be matched
27    // against a remaining occurrence in nums2.
28    const countInNums1 = new Map<number, number>();
29
30    for (const value of nums1) {
31        const available = countInNums2.get(value) ?? 0;
32        if (available > 0) {
33            // Consume one matching occurrence from nums2.
34            countInNums2.set(value, available - 1);
35        } else {
36            // No match available, record this value as a leftover from nums1.
37            countInNums1.set(value, (countInNums1.get(value) ?? 0) + 1);
38        }
39    }
40
41    // Accumulated minimum cost.
42    let answer = 0;
43
44    // Each leftover group in nums1 must be evenly pairable.
45    for (const groupSize of countInNums1.values()) {
46        if (groupSize % 2 === 1) {
47            return -1;
48        }
49        answer += Math.floor(groupSize / 2);
50    }
51
52    // Each leftover group in nums2 must also be evenly pairable.
53    for (const groupSize of countInNums2.values()) {
54        if (groupSize % 2 === 1) {
55            return -1;
56        }
57    }
58
59    return answer;
60}
61

Time and Space Complexity

Time Complexity: O(n), where n is the length of the arrays.

Building cnt2 from nums2 takes O(n) time.
Iterating over nums1 to populate cnt1 and decrement cnt2 takes O(n) time, since each Counter lookup and update is O(1) on average.
Iterating over the values of cnt1 takes at most O(n) time, as the number of distinct keys is bounded by n.
Iterating over the values of cnt2 likewise takes at most O(n) time.

The overall time complexity is therefore O(n).

Space Complexity: O(n), where n is the length of the arrays.

The cnt2 counter stores at most n distinct keys from nums2.
The cnt1 counter stores at most n distinct keys derived from nums1.

Hence the additional space used is O(n).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Counting the cost from both `cnt1` and `cnt2`

The most frequent mistake is adding freq // 2 from both leftover counters when accumulating the answer:

# WRONG — double counts every swap
for freq in count1.values():
    swaps += freq // 2
for freq in count2.values():
    swaps += freq // 2     # <-- this doubles the real cost

Why it's wrong: A single paid swap at index i exchanges nums1[i] with nums2[i]. That one operation simultaneously removes a surplus element from nums1 and deposits the needed element into nums2 (and vice versa). The leftovers in cnt1 and cnt2 are two views of the same imbalance, not two independent problems. Each swap fixes one unit on each side at once, so the surplus in cnt1 already fully describes how many swaps are required.

Solution: Use cnt2 only for the feasibility check (every frequency must be even), and accumulate the cost from cnt1 alone — exactly as the reference code does.

for freq in count1.values():
    if freq % 2 == 1:
        return -1
    swaps += freq // 2     # cost comes from one side only

for freq in count2.values():
    if freq % 2 == 1:
        return -1            # check only, no += swaps

Pitfall 2: Forgetting that each counter must independently be all-even

Some implementations check only cnt1 for odd frequencies and skip cnt2, assuming that if cnt1 is balanced then cnt2 automatically is. This is not guaranteed.

Consider a value x that is surplus only in nums2 (it never appears as a leftover in nums1). Its imbalance lives entirely in cnt2. If that count is odd, the arrays are impossible to balance, but a check that looks only at cnt1 would miss it and return a wrong non-negative answer.

Solution: Validate the odd/even condition on both counters before returning. The pairs of leftover values must line up on each side, so both must be even.

Pitfall 3: Misreading the cost model — thinking within-array swaps cost something

It's tempting to try to "optimize" the free in-array reordering, e.g., counting how many positions differ after sorting. But because in-array swaps are free and unlimited, the actual positions are irrelevant — only the multiset of values in each array matters.

Why it's wrong: Any element can be moved to any slot inside its own array at no cost. The only thing that costs money is changing which array an element belongs to. So the problem reduces purely to counting multiset surpluses, not comparing element positions.

Solution: Work entirely with value counts (Counter), never with indices or sorted-position comparisons. This is precisely why the hash-table approach is both correct and O(n).

Pitfall 4: Mutating a `Counter` and relying on missing-key behavior

The line if count2[value]: reads a key that may not exist. With collections.Counter this safely returns 0 (not a KeyError). If you accidentally use a plain dict, this access raises an exception.

count2 = {}          # plain dict
...
if count2[value]:    # KeyError if value not present!

Solution: Always use Counter (or dict.get(value, 0)) for the lookup so absent values default to 0:

count2 = Counter(nums2)
if count2[value]:    # safe: defaults to 0
    count2[value] -= 1

Note also that reading count2[value] on a Counter does not insert a zero entry the way count2[value] += 0 would, keeping the later iteration over count2.values() clean.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Which of the following is a good use case for backtracking?

Combinatorial problems

Random number generation

Topological sorting

Matrix multiplication

I don't know