Skip to main content
Talentd

Minimum Cost to Equalize Arrays Using Swaps - Solution & Explanation

MediumArrayHash TableGreedyCounting9 min readAsked at: Uber, Shopback
Practice this problem

Problem Statement

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed 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

Video Solution

3868. Minimum Cost to Equalize Arrays Using Swaps | Biweekly Contest 178 | Leetcode • Rapid Syntax • 477 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Minimum Cost to Equalize Arrays Using Swaps with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays