Is Minimum Cost to Equalize Arrays Using Swaps easy or hard?

The problem is typically classified as Medium difficulty. The main challenge is recognizing that direct swaps are not always optimal and that using the global minimum element can reduce cost. Combining counting, sorting, and greedy reasoning is the key insight.

Minimum Cost to Equalize Arrays Using Swaps Python/Java solution

Most implementations follow the same pattern: count frequencies with a dictionary or map, build a list of surplus elements, sort the list, and compute swap costs using the global minimum element rule. The logic translates directly across Python, Java, C++, Go, and TypeScript.

How to solve Minimum Cost to Equalize Arrays Using Swaps in O(n)?

A near-linear solution starts by counting element frequencies in both arrays using a hash map. After verifying that all combined frequencies are even, build a list of surplus elements that must be swapped. Sorting this list and applying a greedy pairing strategy with the global minimum value yields the minimal total cost.

What is the best approach for Minimum Cost to Equalize Arrays Using Swaps?

The most efficient solution uses a hash table to count frequencies and detect mismatches between the arrays. Extra elements from each array are collected, sorted, and paired using a greedy strategy that minimizes swap cost. This approach runs in O(n log n) time due to sorting and uses O(n) additional space.

Is Minimum Cost to Equalize Arrays Using Swaps asked at Google/Amazon/Meta?

Problems involving swap cost minimization and frequency balancing commonly appear in interviews at companies like Amazon, Google, and Meta. Variants typically test counting with hash tables, greedy optimization, and reasoning about global minimum elements during swaps.

What data structure is used in Minimum Cost to Equalize Arrays Using Swaps?

The core data structure is a hash table used to count frequencies of values across both arrays and determine imbalance. Additional structures include an array or list to store mismatched elements and sorting to enable greedy pairing.

What is the time complexity of Minimum Cost to Equalize Arrays Using Swaps?

The optimal algorithm runs in O(n log n) time. Building frequency maps and extracting mismatches takes O(n), while sorting the mismatch list dominates the runtime. Space complexity is O(n) for storing frequency counts and imbalance values.

Description Hints 3 Solution Video 16:14

3868. Minimum Cost to Equalize Arrays Using Swaps

Medium48.7% acceptance2 companies

You are given two integer arrays nums1 and nums2 of size n.

You can perform the following two operations any number of times on these two arrays:

Swap within the same array: Choose two indices i and j. Then, choose either to swap nums1[i] and nums1[j], or nums2[i] and nums2[j]. This operation is free of charge.
Swap between two arrays: Choose an index i. Then, swap nums1[i] and nums2[i]. This operation incurs a cost of 1.

Return an integer denoting the minimum cost to make nums1 and nums2 identical. If this is not possible, return -1.

Example 1:

Input: nums1 = [10,20], nums2 = [20,10]

Output: 0

Explanation:

Swap nums2[0] = 20 and nums2[1] = 10.
- nums2 becomes [10, 20].
- This operation is free of charge.
nums1 and nums2 are now identical. The cost is 0.

Example 2:

Input: nums1 = [10,10], nums2 = [20,20]

Output: 1

Explanation:

Swap nums1[0] = 10 and nums2[0] = 20.
- nums1 becomes [20, 10].
- nums2 becomes [10, 20].
- This operation costs 1.
Swap nums2[0] = 10 and nums2[1] = 20.
- nums2 becomes [20, 10].
- This operation is free of charge.
nums1 and nums2 are now identical. The cost is 1.

Example 3:

Input: nums1 = [10,20], nums2 = [30,40]

Output: -1

Explanation:

It is impossible to make the two arrays identical. Therefore, the answer is -1.

Constraints:

2 <= n == nums1.length == nums2.length <= 8 * 10⁴
1 <= nums1[i], nums2[i] <= 8 * 10⁴

Asked at 2 companies

Shopback Uber

Topics

Hints open one at a time

Hint 1

Since swaps inside the same array are free, positions do not matter; only frequencies matter.

Hint 2

Let cnt1[v] and cnt2[v] be frequencies. If cnt1[v] + cnt2[v] is odd for any v, return -1.

Hint 3

Let diff[v] = abs(cnt1[v] - cnt2[v]). Each cross swap fixes two mismatches, so minimum cost = sum(diff[v]) / 4.

16:14

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def minCost(self, nums1: list[int], nums2: list[int]) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[10,20]
[20,10]

Input

[10,10]
[20,20]

Input

[10,20]
[30,40]

Your code is saved on this device.Solution