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 the minimum total cost such that nums1 and nums2 satisfy the above condition. In case it is not possible, return -1.
Example 1:
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:
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:
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.length1 <= n <= 1051 <= nums1[i], nums2[i] <= nIn #2499 Minimum Total Cost to Make Arrays Unequal, the goal is to ensure that for every index i, nums1[i] != nums2[i] while minimizing the total cost of swaps. A key observation is that only indices where nums1[i] == nums2[i] create conflicts. These positions must participate in swaps to break equality.
A greedy strategy with counting works well. First, collect all conflicting indices and accumulate their costs. While doing this, maintain a frequency map of values causing the conflicts. If one value becomes too dominant among these positions, additional indices (where arrays are already unequal) may be required to safely perform swaps without reintroducing equality.
The algorithm tracks the most frequent conflicting value and ensures enough non-conflicting positions are used when necessary. This combination of hash table counting and greedy index selection keeps the total cost minimal.
The overall solution runs in O(n) time with O(n) auxiliary space for counting and tracking indices.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy with Hash Map Counting | O(n) | O(n) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
How can we check which indices of <code>nums1</code> will be considered for swapping? How to minimize the number of such operations?
It can be seen that greedily swapping values of indices where <code>nums1[i] == nums2[i]</code> is the most optimal choice. How many values cannot be swapped this way?
Find which indices we will swap these remaining values with, and if there are enough such indices.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
If a single value appears too frequently in positions where nums1[i] equals nums2[i], swapping only those indices could recreate equal pairs. Tracking the dominant value helps determine when extra non-conflicting indices must be included to maintain inequality.
Yes, problems like #2499 often appear in advanced interview rounds at large tech companies. They test greedy thinking, frequency counting, and the ability to reason about constraints and edge cases efficiently.
A hash table (or frequency map) is ideal for tracking how often each value appears in conflicting positions. This helps detect if one value dominates and whether additional indices are needed to complete valid swaps.
The optimal approach uses a greedy strategy combined with hash map counting. First handle indices where nums1[i] equals nums2[i], then track the most frequent value among those conflicts. If one value dominates, additional safe indices are selected to avoid forming new equal pairs while minimizing cost.