Skip to content

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
43
class Solution {
 public:
  long long minimumTotalCost(vector<int>& nums1, vector<int>& nums2) {
    const int n = nums1.size();
    long ans = 0;
    int maxFreq = 0;
    int maxFreqNum = 0;
    int shouldBeSwapped = 0;
    vector<int> conflictedNumCount(n + 1);

    // Collect the 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 the 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;
      // The numbers == `maxFreqNum` worsen the result since they increase the
      // `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
42
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 the 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 the 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;
      // The numbers == `maxFreqNum` worsen the result since they increase the
      // `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
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 the 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 the 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
      # The numbers == `maxFreqNum` worsen the result since they increase the
      # `maxFreq`.
      if num1 == maxFreqNum or num2 == maxFreqNum:
        continue
      shouldBeSwapped += 1
      ans += i

    return -1 if maxFreq * 2 > shouldBeSwapped else ans