Scale Engineer

Minimum Total Cost to Make Arrays Unequal

Hard
#2280Time: 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.2 companies
Patterns
GreedyCounting
Data structures
ArrayHash Table
Companies
Flipkartrazorpay

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

// 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    }}

Complexity

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.

Trade-offs

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.

Solutions

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;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem