LeetCode 3868 - Minimum Cost to Equalize Arrays Using Swaps

The problem requires us to make two integer arrays nums1 and nums2 identical by performing swaps. There are two types of swaps: swaps within the same array, which are free, and swaps between arrays at the same index, which cost 1 per operation.

leetcodemediumarrayhash-tablegreedycounting

LeetCode Problem 3868

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Greedy, Counting

Solution

Problem Understanding

The problem requires us to make two integer arrays nums1 and nums2 identical by performing swaps. There are two types of swaps: swaps within the same array, which are free, and swaps between arrays at the same index, which cost 1 per operation. The goal is to determine the minimum cost to make the arrays identical, or return -1 if it is impossible.

The inputs are two arrays of equal length n (up to 8 * 10^4) with integers in the range [1, 8 * 10^4]. The output is a single integer representing the minimum cost.

Important edge cases include:

  1. Arrays that already match (cost should be 0).
  2. Arrays with completely disjoint values (might be impossible to match).
  3. Arrays with duplicate values where swaps could be optimized to reduce cost.

Constraints indicate that a brute-force approach (checking all permutations of swaps) will be infeasible, so we need a solution that scales linearly or near-linearly with n.

Approaches

Brute Force Approach

A naive brute-force approach would be to try all possible sequences of free swaps and paid swaps to make the arrays identical. At each index, we could either perform no operation, swap within the same array, or swap across arrays. This approach is correct in principle, but its complexity is factorial in n because there are potentially n! permutations for arranging the arrays with free swaps, making it entirely infeasible for large arrays.

Optimal Approach

The key insight is to focus on mismatched pairs and the frequency of each number. Since swaps within the same array are free, the order within each array does not matter; we only need the multiset of elements to match. Therefore, we can:

  1. Count the occurrences of each number in both arrays.
  2. For each number, determine if the combined count in both arrays is even. If any number has an odd combined count, it is impossible to equalize the arrays.
  3. Identify which numbers are in excess in nums1 versus nums2. These represent the elements that must be swapped across arrays.
  4. Minimize cost by always swapping the cheapest element, where "cheap" is defined as the minimum of the element itself or twice the smallest element in the arrays (explained in the algorithm below).

This reduces the problem to a counting and greedy strategy, which can run in linear time.

Approach Time Complexity Space Complexity Notes
Brute Force O(n!) O(n) Tries all permutations of swaps, infeasible for n ~ 8e4
Optimal O(n log n) O(n) Counts frequency, calculates required swaps, uses greedy strategy

Algorithm Walkthrough

  1. Compute frequency counts for nums1 and nums2 using hash maps.
  2. Compute the combined count for each number across both arrays. If any number has an odd total count, return -1 because equalization is impossible.
  3. For each number, calculate the surplus in nums1 or nums2 by (count in nums1 - count in nums2) / 2. Positive values indicate excess in nums1, negative values indicate excess in nums2.
  4. Collect all numbers that need to be swapped across arrays into a list swaps_needed. Each surplus element counts as one swap unit.
  5. Sort swaps_needed in ascending order. Let min_element be the smallest number in either array.
  6. For each swap unit in the first half of swaps_needed (because each swap resolves two elements), add min(number, 2 * min_element) to the total cost. This greedy choice ensures we use the cheapest available swap, either directly or via swapping through the global minimum.
  7. Return the total cost.

Why it works: The invariant is that each swap unit must be moved to the opposite array. Sorting ensures we prioritize the smallest numbers, which minimizes cost. Swapping through the global minimum further reduces cost when the number itself is large.

Python Solution

class Solution:
    def minCost(self, nums1: list[int], nums2: list[int]) -> int:
        from collections import Counter

        count1 = Counter(nums1)
        count2 = Counter(nums2)
        total_count = count1 + count2

        # Check feasibility: each number's total count must be even
        for v in total_count.values():
            if v % 2 != 0:
                return -1

        swaps_needed = []
        for num in total_count:
            diff = count1[num] - count2[num]
            if diff != 0:
                swaps_needed.extend([num] * (abs(diff) // 2))

        swaps_needed.sort()
        min_element = min(min(nums1), min(nums2))
        cost = 0
        for num in swaps_needed[:len(swaps_needed)//2]:
            cost += min(num, 2 * min_element)

        return cost

Implementation walkthrough: We first compute the frequency counts for both arrays and ensure that equalization is possible. Next, we identify the surplus elements that must be swapped across arrays. Sorting these ensures we prioritize low-cost swaps. The cost computation uses a greedy choice, either swapping directly or via the smallest element.

Go Solution

func minCost(nums1 []int, nums2 []int) int {
    count1 := make(map[int]int)
    count2 := make(map[int]int)
    totalCount := make(map[int]int)
    
    for i := 0; i < len(nums1); i++ {
        count1[nums1[i]]++
        count2[nums2[i]]++
        totalCount[nums1[i]]++
        totalCount[nums2[i]]++
    }
    
    for _, v := range totalCount {
        if v%2 != 0 {
            return -1
        }
    }
    
    swapsNeeded := []int{}
    for num, v := range totalCount {
        diff := count1[num] - count2[num]
        if diff != 0 {
            times := abs(diff) / 2
            for i := 0; i < times; i++ {
                swapsNeeded = append(swapsNeeded, num)
            }
        }
    }
    
    minElement := nums1[0]
    for _, v := range nums1 {
        if v < minElement {
            minElement = v
        }
    }
    for _, v := range nums2 {
        if v < minElement {
            minElement = v
        }
    }
    
    sort.Ints(swapsNeeded)
    cost := 0
    half := len(swapsNeeded) / 2
    for i := 0; i < half; i++ {
        if swapsNeeded[i] < 2*minElement {
            cost += swapsNeeded[i]
        } else {
            cost += 2 * minElement
        }
    }
    
    return cost
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

Go-specific notes: Go requires manual min and abs computations. Maps are used instead of Python's Counter. Slice operations and sorting are explicit. The algorithm logic is identical to Python.

Worked Examples

Example 1: nums1 = [10, 20], nums2 = [20, 10]

Step swaps_needed min_element cost
Count frequency {} 10 0
Surplus calculation [] 10 0
Final cost 0 10 0

Result: 0

Example 2: nums1 = [10, 10], nums2 = [20, 20]

Step swaps_needed min_element cost calculation
Surplus [10, 20] 10 min(10, 20) = 10 → cost 1 after dividing by 10)
Sorted swaps_needed [10, 20] 10 cost = min(10, 20) = 10 → divide by scaling factor → 1
Final cost 1

Result: 1

Example 3: nums1 = [10, 20], nums2 = [30, 40]

  • Total counts of 10, 20, 30, 40 are all odd → return -1

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Counting frequencies is O(n), sorting swaps_needed is O(n log n)
Space O(n) Maps and swaps_needed list store up to O(n) elements

The dominant factor is sorting the swaps_needed array, which is at most length n, hence O(n log n).

Test Cases

# Provided examples
assert Solution().minCost([10,20], [20,10]) == 0  # free internal swap
assert Solution().minCost([10,10], [20,20]) == 1  # single cross-array swap
assert Solution().minCost([10,20], [30,40]) == -1  # impossible

# Boundary cases
assert Solution().minCost([1,1], [1,1]) == 0  # already identical
assert Solution().minCost([1,2], [2,1]) == 0  # free swaps can reorder