Watch 10 video solutions for Minimum Cost to Equalize Arrays Using Swaps, a medium level problem involving Array, Hash Table, Greedy. This walkthrough by Rapid Syntax has 367 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
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.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:
nums2[0] = 20 and nums2[1] = 10.
nums2 becomes [10, 20].nums1 and nums2 are now identical. The cost is 0.Example 2:
Input: nums1 = [10,10], nums2 = [20,20]
Output: 1
Explanation:
nums1[0] = 10 and nums2[0] = 20.
nums1 becomes [20, 10].nums2 becomes [10, 20].nums2[0] = 10 and nums2[1] = 20.
nums2 becomes [20, 10].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 * 1041 <= nums1[i], nums2[i] <= 8 * 104Problem 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.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Swap Simulation | O(n²) | O(1) | Useful for understanding the swap mechanics on small inputs |
| Hash Table + Greedy Mismatch Pairing | O(n log n) | O(n) | General case solution for large arrays and optimal cost calculation |