# Minimum Total Cost to Make Arrays Unequal
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-total-cost-to-make-arrays-unequal)
Canonical: https://scaleengineer.com/dsa/problems/minimum-total-cost-to-make-arrays-unequal
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Array, Hash Table
**Companies:** [Flipkart](https://scaleengineer.com/companies/flipkart), [razorpay](https://scaleengineer.com/companies/razorpay)
---
## Problem
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.length`
* `1 <= n <= 105`
* `1 <= nums1[i], nums2[i] <= n`

# Approaches
## Brute-Force Backtracking
This approach attempts to solve the problem by exploring all possible ways to resolve the conflicts. It identifies all indices `i` where `nums1[i] == nums2[i]` and then uses a brute-force, recursive method to try all valid pairings for swaps, either between two conflicting indices or between a conflicting and a non-conflicting index. It calculates the cost for each complete set of swaps and finds the minimum among them.
**Time:** Exponential, likely O(S!) or worse, where S is the number of conflicts. This will time out for all but the smallest inputs. · **Space:** O(N) or O(S^2) where S is the number of conflicts, for storing the state and recursion stack.
**Pros:** Guaranteed to find the optimal solution if it runs to completion.
**Cons:** Extremely inefficient due to its exponential time complexity.; Not feasible for the given constraints (`n` up to 10^5).; The logic for handling swaps with non-conflicting indices and ensuring no new conflicts are created adds significant complexity to the implementation.
### Explanation
The fundamental observation is that for every index `i` where `nums1[i] == nums2[i]`, the value `nums1[i]` must be changed. This can only be done by swapping it with another value `nums1[j]`. This brute-force approach systematically tries every possible way to resolve these conflicts.

We can model this as a search problem. Let `S` be the set of conflicting indices. We need to find a sequence of swaps that makes `nums1[i] != nums2[i]` for all `i`. A backtracking algorithm can explore the space of possible swaps. For each unresolved conflict, we can try to swap it with another unresolved conflict or with a non-conflicting index. We would explore all such possibilities, pruning branches that are invalid, and return the minimum cost found.

For instance, a recursive function could take the set of remaining conflicts as input. In each call, it would pick one conflict, try all valid swap partners for it, and recurse on the remaining set of conflicts. The number of ways to pair up conflicts can be very large, leading to a combinatorial explosion.

```java
// This is a conceptual illustration. A full implementation would be very complex and inefficient.
class Solution {
    public long minimumTotalCost(int[] nums1, int[] nums2) {
        // This approach is too slow and complex to implement fully for the given constraints.
        // It would involve a backtracking function like:
        // findMinCost(conflicts, currentCost)
        // where 'conflicts' is a list of indices to resolve.
        // In each step, you'd pick a conflict, try all valid swap partners,
        // and recurse, updating the cost.
        // The number of possibilities makes this approach infeasible.
        return -1; // Placeholder for an infeasible approach
    }
}
```
### Algorithm
1. Identify the set of conflicting indices `S = {i | nums1[i] == nums2[i]}`.
2. The problem is to resolve all conflicts in `S`. Each conflict `i` must be resolved by swapping `nums1[i]` with some `nums1[j]`.
3. This approach explores all possible ways to pair up the conflicting indices for swaps.
4. A recursive backtracking function, say `solve(conflicts_to_resolve)`, is defined.
5. In the function, pick a conflict `i` from the set.
6. Try pairing `i` with every other conflict `j` in the set. For each pair `(i, j)`:
   a. Check if swapping them is valid (i.e., `nums1[i] != nums2[j]` and `nums1[j] != nums2[i]`).
   b. If valid, recursively call `solve` for the remaining conflicts, adding `i+j` to the cost.
7. Also, try pairing `i` with every non-conflicting index `k \notin S`.
   a. Check if swapping them is valid (i.e., `nums1[k]` resolves conflict `i` without creating a new one at `k`).
   b. If valid, recursively call `solve` for remaining conflicts, adding `i+k` to the cost.
8. The base case for the recursion is when there are no more conflicts to resolve, in which case the cost is 0.
9. Keep track of the minimum cost found across all valid sequences of swaps.

## Greedy Approach with Dominant Value
This efficient approach uses a greedy strategy based on analyzing the values at the conflicting indices. It first calculates a base cost by summing all conflicting indices. Then, it identifies the most frequent value (`v_dom`) among these conflicts. The strategy is to resolve as many conflicts as possible by swapping non-dominant conflicts with dominant ones. Any remaining dominant conflicts must be swapped with non-conflicting indices. The algorithm greedily chooses the cheapest available non-conflicting indices for these swaps to minimize the total cost.
**Time:** O(N) because we iterate through the arrays a constant number of times. The map operations take, on average, O(1) time. If we use arrays for frequency counts (since values are bounded by `n`), it's guaranteed O(N). · **Space:** O(N) to store the conflict status, frequency counts, and potential partner indices.
**Pros:** Very efficient, with a linear or near-linear time complexity.; Correctly handles all cases, including impossible scenarios.; The greedy choice is proven to be optimal for this problem structure.
**Cons:** The logic can be subtle to reason about, particularly the calculation of remaining conflicts and the conditions for external swap partners.
### Explanation
The key insight is that the total cost of swaps can be broken down. Any index `i` that is part of a swap `(i, j)` contributes `i` to the total cost. Since every conflicting index must be part of at least one swap, the sum of all conflicting indices is a baseline for the total cost.

The problem then becomes minimizing the sum of the indices of the swap partners.

We can resolve two conflicts `i` and `j` by swapping `nums1[i]` and `nums1[j]` if their values are different. This suggests a greedy strategy: find the value `v_dom` that is most common among all conflicts. Let its frequency be `max_freq`. The `|S| - max_freq` conflicts with other values can be paired up and swapped with `|S| - max_freq` conflicts of value `v_dom`. This resolves `2 * (|S| - max_freq)` conflicts.

The cost for these internal swaps is already accounted for by summing up all indices in `S`.

We are left with `max_freq - (|S| - max_freq) = 2*max_freq - |S|` conflicts of value `v_dom`. These must be swapped with indices `l` from outside the conflict set `S`. To maintain validity, such an `l` must not have `v_dom` as its value in either `nums1` or `nums2`. We find all such valid `l`'s and, to minimize cost, pick the ones with the smallest indices. Their indices are added to our running total cost.

If at any point we don't have enough valid partners, the task is impossible.

```java
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public long minimumTotalCost(int[] nums1, int[] nums2) {
        long totalCost = 0;
        int conflicts = 0;
        Map<Integer, Integer> counts = new HashMap<>();
        int n = nums1.length;
        boolean[] isConflict = new boolean[n];

        for (int i = 0; i < n; i++) {
            if (nums1[i] == nums2[i]) {
                conflicts++;
                totalCost += i;
                counts.put(nums1[i], counts.getOrDefault(nums1[i], 0) + 1);
                isConflict[i] = true;
            }
        }

        if (conflicts == 0) {
            return 0;
        }

        int maxFreq = 0;
        int dominantVal = -1;
        for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
            if (entry.getValue() > maxFreq) {
                maxFreq = entry.getValue();
                dominantVal = entry.getKey();
            }
        }

        int numToSwapExternally = 2 * maxFreq - conflicts;

        if (numToSwapExternally <= 0) {
            return totalCost;
        }

        List<Integer> partners = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (!isConflict[i] && nums1[i] != dominantVal && nums2[i] != dominantVal) {
                partners.add(i);
            }
        }

        if (partners.size() < numToSwapExternally) {
            return -1;
        }

        for (int i = 0; i < numToSwapExternally; i++) {
            totalCost += partners.get(i);
        }

        return totalCost;
    }
}
```
### Algorithm
1. First, identify all conflicting indices `i` where `nums1[i] == nums2[i]`. Let `S` be the set of these indices.
2. Calculate the base cost, which is the sum of all indices in `S`, since each must participate in at least one swap. `total_cost = sum(i for i in S)`.
3. Count the frequency of each value `v` at conflicting indices. Store this in a map or array, `counts[v]`.
4. Find the value `v_dom` that appears most frequently among conflicts (the dominant value), and its frequency `max_freq`.
5. The core idea is to pair up conflicts. A conflict of value `v1` can be resolved by swapping with a conflict of value `v2` if `v1 != v2`. We can resolve `s - max_freq` non-dominant conflicts by pairing them with `s - max_freq` dominant conflicts. This leaves `max_freq - (s - max_freq) = 2*max_freq - s` dominant conflicts unresolved.
6. Let `num_single = 2*max_freq - s`. If `num_single <= 0`, all conflicts can be resolved by swapping within `S`, and the cost is simply `total_cost`. 
7. If `num_single > 0`, these `num_single` conflicts (all of value `v_dom`) must be resolved by swapping with indices `l` outside of `S`.
8. A valid external partner `l` must satisfy: `l \notin S`, `nums1[l] != v_dom`, and `nums2[l] != v_dom`. The first condition ensures we don't create a new conflict for `l`'s original value, and the second ensures we don't create a new `v_dom` conflict at `l`.
9. Collect all such valid partner indices `l` into a list. 
10. If the number of available partners is less than `num_single`, it's impossible to resolve all conflicts. Return -1.
11. Otherwise, to minimize the added cost, greedily pick the `num_single` partners with the smallest indices. Add the sum of these indices to `total_cost`.
12. Return the final `total_cost`.

# Solutions
### Java

```java
class Solution {
public
  long minimumTotalCost(int[] nums1, int[] nums2) {
    long ans = 0;
    int same = 0;
    int n = nums1.length;
    int[] cnt = new int[n + 1];
    for (int i = 0; i < n; ++i) {
      if (nums1[i] == nums2[i]) {
        ans += i;
        ++same;
        ++cnt[nums1[i]];
      }
    }
    int m = 0, lead = 0;
    for (int i = 0; i < cnt.length; ++i) {
      int t = cnt[i] * 2 - same;
      if (t > 0) {
        m = t;
        lead = i;
        break;
      }
    }
    for (int i = 0; i < n; ++i) {
      if (m > 0 && nums1[i] != nums2[i] && nums1[i] != lead &&
          nums2[i] != lead) {
        ans += i;
        --m;
      }
    }
    return m > 0 ? -1 : ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long minimumTotalCost(vector<int> &nums1, vector<int> &nums2) {
    long long ans = 0;
    int same = 0;
    int n = nums1.size();
    int cnt[n + 1];
    memset(cnt, 0, sizeof cnt);
    for (int i = 0; i < n; ++i) {
      if (nums1[i] == nums2[i]) {
        ans += i;
        ++same;
        ++cnt[nums1[i]];
      }
    }
    int m = 0, lead = 0;
    for (int i = 0; i < n + 1; ++i) {
      int t = cnt[i] * 2 - same;
      if (t > 0) {
        m = t;
        lead = i;
        break;
      }
    }
    for (int i = 0; i < n; ++i) {
      if (m > 0 && nums1[i] != nums2[i] && nums1[i] != lead &&
          nums2[i] != lead) {
        ans += i;
        --m;
      }
    }
    return m > 0 ? -1 : ans;
  }
};

```

### Python

```python
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

```