Minimum Total Cost to Make Arrays Unequal

Minimum Total Cost to Make Arrays Unequal

What is this problem about?

The Minimum Total Cost to Make Arrays Unequal problem gives you two arrays of equal length. You can swap elements within arr1 (at a cost equal to the element's index). The goal is to make arr1 and arr2 have no index where arr1[i] == arr2[i]. Find the minimum total cost of swaps needed. This hard coding problem combines greedy thinking with frequency counting and the majority element concept.

Why is this asked in interviews?

Flipkart and Razorpay ask this hard problem because it requires the insight that you need to gather all "problem" elements (where arr1[i] == arr2[i]) and redistribute them, paying attention to whether one value appears so many times that it must be spread to more positions. The array, hash table, counting, and greedy interview pattern is central, and the majority element detection within the swapping pool drives the answer.

Algorithmic pattern used

Greedy with majority element detection. First collect all indices where arr1[i] == arr2[i] — these must be swapped. Sum their costs (indices). The elements at these positions form a pool. If any one value appears more than half the total swapped elements, it can't be redistributed without dragging in more indices from outside the problem set — include additional indices (cheapest first) until no majority element exists. The total cost is the sum of all included indices.

Example explanation

arr1 = [2,2,2,1,3], arr2 = [1,2,2,3,3].

• Conflict at index 1 (arr1[1]=2=arr2[1]), index 2 (arr1[2]=2=arr2[2]), index 4 (arr1[4]=3=arr2[4]).
• Cost so far = 1+2+4 = 7. Pool values: {2,2,3}. Value 2 appears 2 times out of 3 total → majority (2 > 3/2).
• Include index 0 (arr1[0]=2 ≠ arr2[0]=1, but value=2). Now pool: {2,2,2,3}, total=4. 2 appears 3 times (not > 4/2=2... wait 3 > 2, still majority). Include index 3 (arr1[3]=1). Pool: {2,2,2,1,3}, value 2 = 3 out of 5 (not majority). Cost = 7+0+3 = 10.

Common mistakes candidates make

• Not detecting the majority element condition in the swap pool.
• Including extra indices in the wrong order (should add cheapest first = smallest index).
• Forgetting that only indices where arr1[i] == arr2[i] are mandatory to include.
• Off-by-one in the majority condition (strictly more than half).

Interview preparation tip

Hard greedy problems with "majority element" constraints require recognizing when one value's frequency exceeds half the total pool size. The Boyer-Moore majority vote algorithm is useful here. Practice majority element detection in dynamic pools — scenarios where elements are added incrementally and you need to track whether any element dominates. This greedy-plus-majority pattern appears in problems involving frequency balancing, equalization, and redistribution.