Minimum Total Cost to Make Arrays Unequal — LeetCode 2499 Python Solution

The 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.

Example

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:

Python solution

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

Complexity

Pattern: Greedy

Take the locally best option every time — when you can prove that never costs you later. LeetCode 2499. Minimum Total Cost to Make Arrays Unequal is filed here because LeetCode tags it Greedy, which is the vocabulary this hub collects.

The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.

Related problems