Minimum Cost to Equalize Arrays Using Swaps - Video Solutions

Problem Overview: You are given two arrays containing the same number of elements. You can swap elements between arrays, each swap having a cost based on the values involved. The goal is to make both arrays identical while minimizing the total swap cost.

Approach 1: Brute Force Swap Simulation (O(n²) time, O(1) space)

One direct idea is to scan both arrays and repeatedly swap mismatched elements until both arrays match. For every index i, if arr1[i] != arr2[i], search the remaining part of the arrays to find a matching value and perform a swap. This approach requires nested iteration and repeated scanning of the arrays, resulting in O(n²) time complexity.

This method does not scale well because each mismatch may trigger a full search of the remaining elements. It also fails to guarantee minimal cost because swaps are chosen locally rather than globally optimized.

Approach 2: Hash Table + Greedy Cost Minimization (O(n log n) time, O(n) space)

The efficient solution starts with frequency counting. Use a hash table to track how many times each value appears in both arrays. If the total frequency of any value across both arrays is odd, making the arrays identical is impossible because swaps preserve counts.

Next, compute the imbalance between arrays. For each value, determine how many extra occurrences exist in one array versus the other. These extra values represent elements that must participate in swaps. Collect these mismatched values into a list where each element represents half of the surplus difference.

Sort the mismatch list so you always resolve swaps starting with the smallest values. This is where the greedy insight comes in. When swapping two values a and b, the cost is normally min(a, b). However, sometimes it is cheaper to perform two swaps using the globally smallest element in the arrays. The effective cost becomes min(min(a, b), 2 * globalMin).

Iterate through the first half of the sorted mismatch list and pair elements with the corresponding largest mismatches. For each pair, add the minimum achievable cost using the rule above. Sorting ensures the cheapest swaps are handled first, minimizing the final total.

This strategy combines counting, greedy pairing, and careful cost evaluation. The main work is building the mismatch list and sorting it, leading to O(n log n) time complexity and O(n) extra space.

Recommended for interviews: The hash table + greedy approach is what interviewers typically expect. The brute force idea shows you understand the mechanics of swapping, but the optimized method demonstrates real algorithmic thinking: frequency balancing, mismatch extraction, and global cost optimization.