How to Solve Minimum Total Cost to Make Arrays Unequal

Start by scanning both arrays to identify indices where nums1 matches nums2. Use a hash map to count frequencies and determine which elements block a conflict-free arrangement. Apply a greedy strategy to swap indices with the lowest combined costs first, tracking the total cost until all conflicts are resolved or return -1 if impossible.

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

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.

How GhostInterview Helps

• Automatically detects conflict indices using hash lookup for efficient swap planning.
• Guides through greedy selection of low-cost swaps to minimize total cost quickly.
• Validates feasibility and computes minimum total cost without manual trial-and-error.

Topic Pages

• Array
• Hash Table
• Greedy
• Counting

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

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.