#2499

Hard

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Minimum Total Cost to Make Arrays Unequal

Calculate the minimum cost to rearrange nums1 so that no element matches nums2 using optimal swaps and hash counting.

Problem Statement

You are given two integer arrays nums1 and nums2 of length n. You can swap any two elements in nums1, with the cost of a swap equal to the sum of their indices. Your goal is to make nums1 unequal to nums2 at every index with minimal total cost.

Determine the minimum total cost needed so that for all 0 <= i < n, nums1[i] != nums2[i]. If no sequence of swaps can achieve this, return -1.

Examples

Example 1

Input: nums1 = [1,2,3,4,5], nums2 = [1,2,3,4,5]

Output: 10

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

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

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.length
1 <= n <= 105
1 <= nums1[i], nums2[i] <= n

Solution Approach

Identify Conflicting Indices

Scan nums1 and nums2 simultaneously, using a hash table to record which values match at the same index. Track how many times each value causes a conflict to identify which elements must be moved.

Prioritize Low-Cost Swaps

Use a greedy approach to select swaps with the smallest index sum first. Maintain a list of indices that are involved in conflicts and calculate the minimal combination of swaps to eliminate all conflicts.

Check Feasibility and Compute Cost

If any value occurs more than half the array length in conflicts, it may be impossible to resolve. Otherwise, perform swaps iteratively based on the hash counts and index priorities, summing the costs until all nums1[i] != nums2[i].

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on scanning the arrays and resolving conflicts via hash lookups and sorting indices, typically O(n log n) for large n. Space complexity arises from the hash table to count frequencies, O(n).

What Interviewers Usually Probe

Do you notice repeated values that block a solution?
How can you efficiently identify which indices to swap first?
What is the minimal cost approach for handling multiple conflicts?

Common Pitfalls or Variants

Common pitfalls

Failing to account for repeated values that exceed half the array length, making a solution impossible.
Swapping indices without considering combined cost can produce non-optimal total cost.
Ignoring updates to the hash table after each swap can cause incorrect conflict tracking.

Follow-up variants

Return the actual sequence of swaps instead of just the total cost.
Allow swaps between nums1 and nums2 instead of only within nums1.
Extend to multiple arrays where each must differ from all others at every index.

FAQ

What is the minimum total cost to make arrays unequal problem about?

It asks to rearrange nums1 using swaps so that no element matches nums2 at the same index while minimizing the sum of swap indices.

Can I solve this problem without hash tables?

Using hash tables is essential to efficiently track conflicts and element frequencies for the greedy swap strategy.

Why do repeated values make the solution impossible?

If any value appears more than half of the conflict positions, there are not enough alternative positions to swap without creating new conflicts.

Is a greedy approach always optimal here?

Yes, prioritizing swaps with the smallest index sums ensures the minimal total cost given the conflict counts.

How does array scanning plus hash lookup pattern help?

It quickly identifies conflicting indices and counts element frequencies, which are crucial for planning minimal-cost swaps efficiently.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

class Solution:
    def minimumTotalCost(self, nums1: List[int], nums2: List[int]) -> int:
        ans = same = 0
        cnt = Counter()
        for i, (a, b) in enumerate(zip(nums1, nums2)):
            if a == b:
                same += 1
                ans += i
                cnt[a] += 1

        m = lead = 0
        for k, v in cnt.items():
            if v * 2 > same:
                m = v * 2 - same
                lead = k
                break
        for i, (a, b) in enumerate(zip(nums1, nums2)):
            if m and a != b and a != lead and b != lead:
                ans += i
                m -= 1
        return -1 if m else ans

Continue Practicing

#2244 minimum rounds to complete all tasks #2170 minimum operations to make the array alternating #2856 minimum array length after pair removals