# 2499. Minimum Total Cost to Make Arrays Unequal

• Time: $O(n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 class Solution { public: long long minimumTotalCost(vector& nums1, vector& nums2) { const int n = nums1.size(); long long ans = 0; int maxFreq = 0; int maxFreqNum = 0; int shouldBeSwapped = 0; vector conflictedNumCount(n + 1); // Collect indices i s.t. nums1[i] == nums2[i] and record their maxFreq // and maxFreqNum. for (int i = 0; i < n; ++i) if (nums1[i] == nums2[i]) { const int conflictedNum = nums1[i]; if (++conflictedNumCount[conflictedNum] > maxFreq) { maxFreq = conflictedNumCount[conflictedNum]; maxFreqNum = conflictedNum; } ++shouldBeSwapped; ans += i; } // Collect indices with nums1[i] != nums2[i] that contribute less cost. // This can be greedily achieved by iterating from 0 to n - 1. for (int i = 0; i < n; ++i) { // Since we have over maxFreq * 2 spaces, maxFreqNum can be // successfully distributed, so no need to collectextra spaces. if (maxFreq * 2 <= shouldBeSwapped) break; if (nums1[i] == nums2[i]) continue; // Nums == maxFreqNum worsen the result since they increase maxFreq. if (nums1[i] == maxFreqNum || nums2[i] == maxFreqNum) continue; ++shouldBeSwapped; ans += i; } return maxFreq * 2 > shouldBeSwapped ? -1 : ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 class Solution { public long minimumTotalCost(int[] nums1, int[] nums2) { final int n = nums1.length; long ans = 0; int maxFreq = 0; int maxFreqNum = 0; int shouldBeSwapped = 0; int[] conflictedNumCount = new int[n + 1]; // Collect indices i s.t. nums1[i] == nums2[i] and record their maxFreq // and maxFreqNum. for (int i = 0; i < n; ++i) if (nums1[i] == nums2[i]) { final int conflictedNum = nums1[i]; if (++conflictedNumCount[conflictedNum] > maxFreq) { maxFreq = conflictedNumCount[conflictedNum]; maxFreqNum = conflictedNum; } ++shouldBeSwapped; ans += i; } // Collect indices with nums1[i] != nums2[i] that contribute less cost. // This can be greedily achieved by iterating from 0 to n - 1. for (int i = 0; i < n; ++i) { // Since we have over maxFreq * 2 spaces, maxFreqNum can be // successfully distributed, so no need to collectextra spaces. if (maxFreq * 2 <= shouldBeSwapped) break; if (nums1[i] == nums2[i]) continue; // Nums == maxFreqNum worsen the result since they increase maxFreq. if (nums1[i] == maxFreqNum || nums2[i] == maxFreqNum) continue; ++shouldBeSwapped; ans += i; } return maxFreq * 2 > shouldBeSwapped ? -1 : ans; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 class Solution: def minimumTotalCost(self, nums1: List[int], nums2: List[int]) -> int: n = len(nums1) ans = 0 maxFreq = 0 maxFreqNum = 0 shouldBeSwapped = 0 conflictedNumCount = [0] * (n + 1) # Collect indices i s.t. num1 == num2 and record their maxFreq # and maxFreqNum. for i, (num1, num2) in enumerate(zip(nums1, nums2)): if num1 == num2: conflictedNum = num1 conflictedNumCount[conflictedNum] += 1 if conflictedNumCount[conflictedNum] > maxFreq: maxFreq = conflictedNumCount[conflictedNum] maxFreqNum = conflictedNum shouldBeSwapped += 1 ans += i # Collect indices with num1 != num2 that contribute less cost. # This can be greedily achieved by iterating from 0 to n - 1. for i, (num1, num2) in enumerate(zip(nums1, nums2)): # Since we have over maxFreq * 2 spaces, maxFreqNum can be # successfully distributed, so no need to collectextra spaces. if maxFreq * 2 <= shouldBeSwapped: break if num1 == num2: continue # Nums == maxFreqNum worsen the result since they increase maxFreq. if num1 == maxFreqNum or num2 == maxFreqNum: continue shouldBeSwapped += 1 ans += i return -1 if maxFreq * 2 > shouldBeSwapped else ans