Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2499.html
2499. Minimum Total Cost to Make Arrays Unequal
- Difficulty: Hard.
- Related Topics: Array, Greedy.
- Similar Questions: .
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
. 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
Solution (Java, C++, Python)
-
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; } }
-
class Solution { public: long long minimumTotalCost(vector<int>& nums1, vector<int>& nums2) { long long ans = 0; int same = 0; int n = nums1.size(); int cnt[n + 1]; memset(cnt, 0, sizeof cnt); 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 < n + 1; ++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; } };
-
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
-
func minimumTotalCost(nums1 []int, nums2 []int) (ans int64) { same, n := 0, len(nums1) cnt := make([]int, n+1) for i, a := range nums1 { b := nums2[i] if a == b { same++ ans += int64(i) cnt[a]++ } } var m, lead int for i, v := range cnt { if t := v*2 - same; t > 0 { m = t lead = i break } } for i, a := range nums1 { b := nums2[i] if m > 0 && a != b && a != lead && b != lead { ans += int64(i) m-- } } if m > 0 { return -1 } return ans }
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).