Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Minimum Cost to Equalize Arrays Using Swaps solution and explanation

MediumArrayCountingGreedyHash Table5 min read48.7% acceptanceUpdated 24 Mar 2026
Asked atShopbackUber
Practise Minimum Cost to Equalize Arrays Using Swaps
16:14
3868. Minimum Cost to Equalize Arrays Using Swaps | Biweekly Contest 178 | LeetcodeRapid Syntax · 16:14 · 477 viewsWatch on YouTube
9 more videos on this problem
  1. 3868. Minimum Cost to Equalize Arrays Using Swaps | Biweekly Contest 178 | LeetcodeRapid Syntax · 16:14 · 477 views
  2. LeetCode Biweekly Contest 178 | Problem C | Minimum Cost to Equalize Arrays using Swaps Solution.Pretest Passed · 5:13 · 362 views
  3. 3868. Minimum Cost to Equalize Arrays Using Swaps (Leetcode Medium)Programming Live with Larry · 9:43 · 143 views
  4. LeetCode 3868 | Minimum Cost to Equalize Arrays Using Swaps | Java | HindiCode Kage · 11:51 · 113 views
  5. LeetCode Problem 3868 | Minimum Cost to Equalize Arrays Using SwapsRepovive TV · 13:20 · 101 views
  6. Biweekly Contest 178 Q3 minimum cost to equalize arrays using swapsUnbound Coder · 11:32 · 32 views
  7. LeetCode 3868 | Minimum Cost to Equalize Arrays Using Swaps | Biweekly Contest 178 | Java CodeSatyam Sharma Coder · 16:47 · 24 views
  8. Minimum Cost to Equalize Arrays Using Swaps | Leetcode 3868 | Explanation With Code | Javacodewithsitaram · 18:52 · 18 views
  9. Minimum Cost to Equalize Arrays Using Swaps | LeetCode Medium Solution | Biweekly Contest 178CodingHelp · 7:14 · 10 views
  10. [Live Problem Solving] 3868. Minimum Cost to Equalize Arrays Using Swapscookedcoder67 · 12:36 · 8 views

The problem

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

You can perform the following two operations any number of times on these two arrays:

  • Swap within the same array: Choose two indices i and j. Then, choose either to swap nums1[i] and nums1[j], or nums2[i] and nums2[j]. This operation is free of charge.
  • Swap between two arrays: Choose an index i. Then, swap nums1[i] and nums2[i]. This operation incurs a cost of 1.

Return an integer denoting the minimum cost to make nums1 and nums2 identical. If this is not possible, return -1.

Example 1:

Input: nums1 = [10,20], nums2 = [20,10]

Output: 0

Explanation:

  • Swap nums2[0] = 20 and nums2[1] = 10.
    • nums2 becomes [10, 20].
    • This operation is free of charge.
  • nums1 and nums2 are now identical. The cost is 0.

Example 2:

Input: nums1 = [10,10], nums2 = [20,20]

Output: 1

Explanation:

  • Swap nums1[0] = 10 and nums2[0] = 20.
    • nums1 becomes [20, 10].
    • nums2 becomes [10, 20].
    • This operation costs 1.
  • Swap nums2[0] = 10 and nums2[1] = 20.
    • nums2 becomes [20, 10].
    • This operation is free of charge.
  • nums1 and nums2 are now identical. The cost is 1.

Example 3:

Input: nums1 = [10,20], nums2 = [30,40]

Output: -1

Explanation:

It is impossible to make the two arrays identical. Therefore, the answer is -1.

Constraints:

  • 2 <= n == nums1.length == nums2.length <= 8 * 104
  • 1 <= nums1[i], nums2[i] <= 8 * 104

Approach overview

Problem Overview: You are given two arrays containing the same number of elements. You can swap elements between arrays, each swap having a cost based on the values involved. The goal is to make both arrays identical while minimizing the total swap cost.

Approach 1: Brute Force Swap Simulation (O(n²) time, O(1) space)

One direct idea is to scan both arrays and repeatedly swap mismatched elements until both arrays match. For every index i, if arr1[i] != arr2[i], search the remaining part of the arrays to find a matching value and perform a swap. This approach requires nested iteration and repeated scanning of the arrays, resulting in O(n²) time complexity.

This method does not scale well because each mismatch may trigger a full search of the remaining elements. It also fails to guarantee minimal cost because swaps are chosen locally rather than globally optimized.

Approach 2: Hash Table + Greedy Cost Minimization (O(n log n) time, O(n) space)

The efficient solution starts with frequency counting. Use a hash table to track how many times each value appears in both arrays. If the total frequency of any value across both arrays is odd, making the arrays identical is impossible because swaps preserve counts.

Next, compute the imbalance between arrays. For each value, determine how many extra occurrences exist in one array versus the other. These extra values represent elements that must participate in swaps. Collect these mismatched values into a list where each element represents half of the surplus difference.

Sort the mismatch list so you always resolve swaps starting with the smallest values. This is where the greedy insight comes in. When swapping two values a and b, the cost is normally min(a, b). However, sometimes it is cheaper to perform two swaps using the globally smallest element in the arrays. The effective cost becomes min(min(a, b), 2 * globalMin).

Iterate through the first half of the sorted mismatch list and pair elements with the corresponding largest mismatches. For each pair, add the minimum achievable cost using the rule above. Sorting ensures the cheapest swaps are handled first, minimizing the final total.

This strategy combines counting, greedy pairing, and careful cost evaluation. The main work is building the mismatch list and sorting it, leading to O(n log n) time complexity and O(n) extra space.

Recommended for interviews: The hash table + greedy approach is what interviewers typically expect. The brute force idea shows you understand the mechanics of swapping, but the optimized method demonstrates real algorithmic thinking: frequency balancing, mismatch extraction, and global cost optimization.

Solution

We can use two hash tables cnt1 and cnt2 to count the occurrences of each integer in the two arrays. During the counting process, we can directly cancel out the occurrences of integers that appear in both arrays. Finally, we check whether the occurrence count of every integer in both hash tables is even. If any integer has an odd count, we return -1. Otherwise, we compute the sum of half the occurrence counts of all integers in cnt1, which gives the minimum cost.

The time complexity is O(n), and the space complexity is O(n), where n is the length of the arrays.

class Solution:
    def minCost(self, nums1: list[int], nums2: list[int]) -> int:
        cnt2 = Counter(nums2)
        cnt1 = Counter()
        for x in nums1:
            if cnt2[x]:
                cnt2[x] -= 1
            else:
                cnt1[x] += 1
        ans = 0
        for v in cnt1.values():
            if v % 2 == 1:
                return -1
            ans += v // 2
        for v in cnt2.values():
            if v % 2 == 1:
                return -1
        return ans
class Solution {
    public int minCost(int[] nums1, int[] nums2) {
        Map<Integer, Integer> cnt2 = new HashMap<>();
        for (int x : nums2) {
            cnt2.merge(x, 1, Integer::sum);
        }

        Map<Integer, Integer> cnt1 = new HashMap<>();
        for (int x : nums1) {
            int c = cnt2.getOrDefault(x, 0);
            if (c > 0) {
                cnt2.put(x, c - 1);
            } else {
                cnt1.merge(x, 1, Integer::sum);
            }
        }

        int ans = 0;

        for (int v : cnt1.values()) {
            if ((v & 1) == 1) {
                return -1;
            }
            ans += v / 2;
        }

        for (int v : cnt2.values()) {
            if ((v & 1) == 1) {
                return -1;
            }
        }

        return ans;
    }
}
class Solution {
public:
    int minCost(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> cnt2;
        for (int x : nums2) {
            ++cnt2[x];
        }

        unordered_map<int, int> cnt1;
        for (int x : nums1) {
            if (cnt2[x] > 0) {
                --cnt2[x];
            } else {
                ++cnt1[x];
            }
        }

        int ans = 0;

        for (auto& [_, v] : cnt1) {
            if (v & 1) {
                return -1;
            }
            ans += v / 2;
        }

        for (auto& [_, v] : cnt2) {
            if (v & 1) {
                return -1;
            }
        }

        return ans;
    }
};
function minCost(nums1: number[], nums2: number[]): number {
    const cnt2 = new Map<number, number>();

    for (const x of nums2) {
        cnt2.set(x, (cnt2.get(x) ?? 0) + 1);
    }

    const cnt1 = new Map<number, number>();

    for (const x of nums1) {
        const c = cnt2.get(x) ?? 0;
        if (c > 0) {
            cnt2.set(x, c - 1);
        } else {
            cnt1.set(x, (cnt1.get(x) ?? 0) + 1);
        }
    }

    let ans = 0;

    for (const v of cnt1.values()) {
        if (v % 2 === 1) {
            return -1;
        }
        ans += Math.floor(v / 2);
    }

    for (const v of cnt2.values()) {
        if (v % 2 === 1) {
            return -1;
        }
    }

    return ans;
}
func minCost(nums1 []int, nums2 []int) int {
	cnt2 := map[int]int{}
	for _, x := range nums2 {
		cnt2[x]++
	}

	cnt1 := map[int]int{}
	for _, x := range nums1 {
		if cnt2[x] > 0 {
			cnt2[x]--
		} else {
			cnt1[x]++
		}
	}

	ans := 0

	for _, v := range cnt1 {
		if v%2 == 1 {
			return -1
		}
		ans += v / 2
	}

	for _, v := range cnt2 {
		if v%2 == 1 {
			return -1
		}
	}

	return ans
}
Try this approach in the editor

Complexity analysis

ApproachTimeSpaceWhen to Use
Brute Force Swap SimulationO(n²)O(1)Useful for understanding the swap mechanics on small inputs
Hash Table + Greedy Mismatch PairingO(n log n)O(n)General case solution for large arrays and optimal cost calculation

Frequently asked questions

Is Minimum Cost to Equalize Arrays Using Swaps easy or hard?

The problem is typically classified as Medium difficulty. The main challenge is recognizing that direct swaps are not always optimal and that using the global minimum element can reduce cost. Combining counting, sorting, and greedy reasoning is the key insight.

Minimum Cost to Equalize Arrays Using Swaps Python/Java solution

Most implementations follow the same pattern: count frequencies with a dictionary or map, build a list of surplus elements, sort the list, and compute swap costs using the global minimum element rule. The logic translates directly across Python, Java, C++, Go, and TypeScript.

How to solve Minimum Cost to Equalize Arrays Using Swaps in O(n)?

A near-linear solution starts by counting element frequencies in both arrays using a hash map. After verifying that all combined frequencies are even, build a list of surplus elements that must be swapped. Sorting this list and applying a greedy pairing strategy with the global minimum value yields the minimal total cost.

What is the best approach for Minimum Cost to Equalize Arrays Using Swaps?

The most efficient solution uses a hash table to count frequencies and detect mismatches between the arrays. Extra elements from each array are collected, sorted, and paired using a greedy strategy that minimizes swap cost. This approach runs in O(n log n) time due to sorting and uses O(n) additional space.

Is Minimum Cost to Equalize Arrays Using Swaps asked at Google/Amazon/Meta?

Problems involving swap cost minimization and frequency balancing commonly appear in interviews at companies like Amazon, Google, and Meta. Variants typically test counting with hash tables, greedy optimization, and reasoning about global minimum elements during swaps.

What data structure is used in Minimum Cost to Equalize Arrays Using Swaps?

The core data structure is a hash table used to count frequencies of values across both arrays and determine imbalance. Additional structures include an array or list to store mismatched elements and sorting to enable greedy pairing.

What is the time complexity of Minimum Cost to Equalize Arrays Using Swaps?

The optimal algorithm runs in O(n log n) time. Building frequency maps and extracting mismatches takes O(n), while sorting the mismatch list dominates the runtime. Space complexity is O(n) for storing frequency counts and imbalance values.

Comments

Now write it yourselfClose this page and solve Minimum Cost to Equalize Arrays Using Swaps in the editor, without looking.
Practise Minimum Cost to Equalize Arrays Using Swaps