Minimum Total Cost to Make Arrays Unequal

Hard Arrays & Hashing Greedy Original on LeetCode

Reported atRazorpay

Minimum Total Cost to Make Arrays Unequal is a hard arrays & hashing problem solved with the greedy pattern. The best approach, optimal (greedy with the dominant value), runs in O(n) time and O(n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (shortest path over arrangements) up.

Problem

You are given two integer arrays nums1 and nums2 of the same length n. In one operation you may swap the values at any two indices i and j of nums1; that operation costs i + j.

Your goal is to reach a state where nums1[i] != nums2[i] holds for every index i. Return the minimum total cost of the operations needed, or -1 if it cannot be done.

Examples

Example 1

Input
nums1 = [2, 2, 1, 3], nums2 = [2, 2, 3, 1]
Output
6
Why
Swap indices 0 and 2 (cost 2), then 1 and 3 (cost 4): nums1 becomes [1, 3, 2, 2], which differs from nums2 everywhere.

Example 2

Input
nums1 = [1, 2, 3], nums2 = [1, 2, 3]
Output
3
Why
Swap 0 and 1 (cost 1), then 0 and 2 (cost 2): nums1 = [3, 1, 2].

Example 3

Input
nums1 = [1, 1, 2], nums2 = [1, 1, 1]
Output
-1
Why
Two 1s in nums1 must avoid three positions that all hold 1 in nums2, but only index 2 is free of 1s.

Constraints

  • n == nums1.length == nums2.length
  • 1 <= n <= 10^5
  • 1 <= nums1[i], nums2[i] <= n

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (shortest path over arrangements)O(n! · n²)O(n! · n)
Optimal (greedy with the dominant value)O(n)O(n)

1Brute force (shortest path over arrangements)

TimeO(n! · n²)Up to n! arrangements, each relaxing n(n - 1) / 2 swaps.
SpaceO(n! · n)Every reached arrangement is stored with its distance.

Treat every arrangement of nums1 as a node of a graph, with an edge for each swap (i, j) weighted i + j. Run a shortest-path search from the starting arrangement and stop at the first arrangement that differs from nums2 at every index. All weights are small positive integers, so a bucket queue (one list per total cost) works like Dijkstra without a heap. Only feasible for very small n.

  1. dist[start] = 0; put start in bucket 0.
  2. For cost d = 0, 1, 2, …: take each arrangement in bucket d whose stored distance is still d.
  3. If it differs from nums2 everywhere, return d.
  4. Otherwise, for every pair i < j with different values, swap them; if d + i + j improves that arrangement's distance, record it and put it in bucket d + i + j.
  5. If the buckets run out, return -1.
class Solution {
    public long minimumTotalCost(int[] nums1, int[] nums2) {
        int n = nums1.length;
        Map<String, Integer> dist = new HashMap<>();
        List<List<int[]>> buckets = new ArrayList<>();
        buckets.add(new ArrayList<>());
        buckets.get(0).add(nums1.clone());
        dist.put(Arrays.toString(nums1), 0);
        for (int d = 0; d < buckets.size(); d++) {
            for (int[] state : buckets.get(d)) {
                if (dist.get(Arrays.toString(state)) != d) continue;
                boolean ok = true;
                for (int i = 0; i < n; i++) {
                    if (state[i] == nums2[i]) { ok = false; break; }
                }
                if (ok) return d;
                for (int i = 0; i < n; i++) {
                    for (int j = i + 1; j < n; j++) {
                        if (state[i] == state[j]) continue;
                        int[] next = state.clone();
                        next[i] = state[j];
                        next[j] = state[i];
                        String key = Arrays.toString(next);
                        int nd = d + i + j;
                        if (nd < dist.getOrDefault(key, Integer.MAX_VALUE)) {
                            dist.put(key, nd);
                            while (buckets.size() <= nd) buckets.add(new ArrayList<>());
                            buckets.get(nd).add(next);
                        }
                    }
                }
            }
        }
        return -1;
    }
}

2Optimal (greedy with the dominant value)

TimeO(n)Two linear passes over the arrays.
SpaceO(n)A frequency array over the values 1..n.

Every bad index (where nums1[i] == nums2[i]) has to be touched by a swap, so their index sum is a lower bound. That bound is reachable whenever no single value occupies more than half of the bad indices: the bad values can then be shuffled among themselves (routing swaps through index 0 makes each index pay once) so that no value lands on its own spot. If a value v appears at more than half of the bad indices, borrow good indices in increasing order, but only those where neither array holds v, until v is at most half; each borrowed index adds its own cost. If there are not enough such indices, it is impossible.

  1. For each i with nums1[i] == nums2[i]: cost += i, bad++, freq[nums1[i]]++; track the value dom with the highest freq.
  2. For i = 0..n - 1 while 2 · freq[dom] > bad:
  3. If nums1[i] != nums2[i] and neither equals dom, cost += i and bad++.
  4. Return -1 if 2 · freq[dom] > bad still holds, else cost.
class Solution {
    public long minimumTotalCost(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int[] freq = new int[n + 1];
        long cost = 0;
        int bad = 0, dom = 0;
        for (int i = 0; i < n; i++) {
            if (nums1[i] == nums2[i]) {
                cost += i;
                bad++;
                int v = nums1[i];
                freq[v]++;
                if (freq[v] > freq[dom]) dom = v;
            }
        }
        int f = freq[dom];
        for (int i = 0; i < n && 2 * f > bad; i++) {
            if (nums1[i] != nums2[i] && nums1[i] != dom && nums2[i] != dom) {
                cost += i;
                bad++;
            }
        }
        return 2 * f > bad ? -1 : cost;
    }
}

Edge cases to test

  • No index has nums1[i] == nums2[i]: the answer is 0
  • A single element that matches: impossible, return -1
  • One value fills more than half of the clashing indices, so extra indices must be pulled in
  • The total cost can exceed the 32-bit range for large n

Hints

Hint 1

Call an index bad if nums1[i] == nums2[i]. Every bad index must take part in at least one swap, so the sum of the bad indices is a lower bound. When can you reach it?

Hint 2

Among the bad indices, swapping values around in a cycle that routes through index 0 costs each index exactly once. This works unless one value v appears at more than half of the bad indices.

Hint 3

If v dominates, add good indices j (smallest first) where neither nums1[j] nor nums2[j] equals v, until v is at most half. If you run out, the answer is -1.

FAQ

What is the best time complexity for Minimum Total Cost to Make Arrays Unequal?

Optimal (greedy with the dominant value) runs in O(n) time and O(n) extra space. Two linear passes over the arrays.

Which pattern does Minimum Total Cost to Make Arrays Unequal use?

It is a arrays & hashing problem that uses the greedy pattern. Other problems with the same pattern: Integer to Roman, Jump Game II, Jump Game.

Is there a brute force solution for Minimum Total Cost to Make Arrays Unequal?

Yes. Brute force (shortest path over arrangements) takes O(n! · n²) time and O(n! · n) space. Treat every arrangement of nums1 as a node of a graph, with an edge for each swap (i, j) weighted i + j.

Which edge cases should I test for Minimum Total Cost to Make Arrays Unequal?

No index has nums1[i] == nums2[i]: the answer is 0; A single element that matches: impossible, return -1; One value fills more than half of the clashing indices, so extra indices must be pulled in; The total cost can exceed the 32-bit range for large n.