We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Total Cost to Make Arrays Unequal

Number: 2592

Difficulty: Hard

Paid? No

Companies: Flipkart, razorpay

Problem Description

Given two equal-length arrays nums1 and nums2, in one operation you may swap any two indices in nums1 at a cost equal to the sum of those indices. The goal is to perform a series of such swaps so that for every index i, nums1[i] ≠ nums2[i]. Return the minimum total cost to achieve this; if it is impossible, return -1.

Key Insights

  • Identify the conflict indices where nums1[i] equals nums2[i] (these positions must be fixed).
  • A swap changes two positions in nums1. The challenge is to choose swaps that resolve conflicts without inadvertently causing new conflicts.
  • The swap cost is based solely on the indices chosen, so pairing lower indices with lower indices (or judiciously pairing a low value with a high value) can reduce the overall cost.
  • Frequency analysis on conflicting values is needed: if one value is overly dominant in conflict positions, there might not exist enough “safe” positions to swap with.
  • Sorting conflict indices helps in aiming for minimal cost by considering the indices in order.
  • Sometimes a leftover conflict (if conflicts count is odd) may be fixed by swapping with a non-conflict index that does not create a new conflict.

Space and Time Complexity

Time Complexity: O(n log n) – due to sorting of conflict indices and potential iterations over n elements. Space Complexity: O(n) – for storing the list of conflict indices and frequency count.

Solution

The approach starts by iterating through all indices to record those indices where nums1[i] equals nums2[i] (the conflict indices). Next, count the frequency of each value among these conflicts. If any value appears too frequently (beyond the limit that can potentially be fixed), the answer is -1.

After confirming feasibility, sort the conflict indices so that when pairing them, the sum (i.e., swap cost) is minimized. Pair the smallest index with the largest, the next smallest with the next largest, and so on. If there is an unpaired conflict (in the case of an odd number of conflicts), try to swap that index with a non-conflict index that does not reintroduce a conflict.

This greedy pairing combined with frequency checking helps ensure that the total cost is minimized while achieving the condition nums1[i] ≠ nums2[i] for every index.

Code Solutions

# Python solution with line-by-line comments
def minimumTotalCost(nums1, nums2):
    n = len(nums1)
    conflicts = []  # indices where nums1 and nums2 are equal
    for i in range(n):
        if nums1[i] == nums2[i]:
            conflicts.append(i)
    
    # No conflicts => no cost needed
    if not conflicts:
        return 0

    # Count frequency of conflicting values
    from collections import Counter
    conflict_freq = Counter(nums1[i] for i in conflicts)
    
    # Check if any one value in conflict exceeds the allowable limit
    if max(conflict_freq.values()) > (len(conflicts) // 2 + len(conflicts) % 2):
        return -1

    # Sort conflict indices for a cost efficient pairing strategy
    conflicts.sort()
    
    total_cost = 0
    left = 0
    right = len(conflicts) - 1
    
    # Greedily pair conflicts: swap the smallest with the largest index
    while left < right:
        total_cost += conflicts[left] + conflicts[right]
        left += 1
        right -= 1
    
    # If an unpaired conflict remains, try to swap with a safe non-conflict index.
    if left == right:
        conflict_index = conflicts[left]
        for i in range(n):
            if i not in conflicts and nums1[i] != nums2[conflict_index]:
                total_cost += i + conflict_index
                break
        else:
            # No valid non-conflict index found for swap.
            return -1
            
    return total_cost

# Example usage:
print(minimumTotalCost([1,2,3,4,5], [1,2,3,4,5]))  # Expected output: 10
← Back to All Questions