HardNo. 2499
Minimum Total Cost to Make Arrays Unequal — LeetCode 2499 Python Solution
- Pattern
- Greedy
- Topics
- Greedy, Array, Hash Table, Counting
- Reading time
- 4 min
- Source
- leetcode.com
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 ansComplexity
- Time
- O(n)
- Space · auxiliary
- O(n)
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
| No. | Problem | Difficulty |
|---|---|---|
| 0621 | Task Scheduler | Medium |
| 1054 | Distant Barcodes | Medium |
| 1090 | Largest Values From Labels | Medium |
| 1481 | Least Number of Unique Integers after K Removals | Medium |
| 1775 | Equal Sum Arrays With Minimum Number of Operations | Medium |
| 2131 | Longest Palindrome by Concatenating Two Letter Words | Medium |
Frequently asked questions
- How hard is LeetCode 2499. Minimum Total Cost to Make Arrays Unequal?
LeetCode 2499. Minimum Total Cost to Make Arrays Unequal is rated Hard on LeetCode.
- What is the time complexity of LeetCode 2499. Minimum Total Cost to Make Arrays Unequal?
The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 2499. Minimum Total Cost to Make Arrays Unequal?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 2499. Minimum Total Cost to Make Arrays Unequal cover?
LeetCode 2499. Minimum Total Cost to Make Arrays Unequal is tagged Greedy, Array, Hash Table and Counting on LeetCode.