How to solve LeetCode 2499 (Minimum Total Cost to Make Arrays Unequal)?

This page provides optimized solutions for LeetCode problem 2499 (Minimum Total Cost to Make Arrays Unequal) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test and refine your code.

LeetCode 2499: Minimum Total Cost to Make Arrays Unequal Solution

Problem Description

Explanation:

To solve this problem, we need to find the minimum total cost of performing swap operations such that nums1[i] != nums2[i] for all 0 <= i <= n-1. We can achieve this by iterating through the arrays and calculating the cost for each index where the values are equal. We need to swap these values to make them unequal. If it is not possible to make the arrays unequal, we return -1.

The algorithmic idea involves identifying the indices where nums1[i] == nums2[i] and then sorting these indices based on the difference of the values at those indices. We then use a greedy approach to swap the values at these indices with the smallest cost.

Steps:

Iterate through the arrays and find the indices where nums1[i] == nums2[i].
Store these indices and sort them based on the absolute difference of the values at those indices.
Iterate through the sorted indices and swap the values with the smallest cost.
Keep track of the total cost incurred.
If all indices are successfully swapped, return the total cost. Otherwise, return -1.

Time Complexity:

The time complexity of this algorithm is O(n * log(n)) where n is the length of the arrays.

Space Complexity:

The space complexity is O(n) to store the indices where swaps are needed.

Solutions

import java.util.*;

class Solution {
    public int minOperations(int[] nums1, int[] nums2) {
        int n = nums1.length;
        List<Integer> indices = new ArrayList<>();
        
        for (int i = 0; i < n; i++) {
            if (nums1[i] == nums2[i]) {
                indices.add(i);
            }
        }
        
        if (indices.size() == 0) {
            return 0;
        }
        
        Collections.sort(indices, (a, b) -> Integer.compare(Math.abs(nums1[b] - nums2[b]), Math.abs(nums1[a] - nums2[a])));
        
        int cost = 0;
        for (int index : indices) {
            if (nums1[index] < nums2[index]) {
                if (!swap(nums1, nums2, index))
                    return -1;
            } else {
                if (!swap(nums2, nums1, index))
                    return -1;
            }
            cost++;
        }
        
        return cost;
    }
    
    private boolean swap(int[] arr1, int[] arr2, int index) {
        int diff = Math.abs(arr1[index] - arr2[index]);
        if (arr1[index] < arr2[index]) {
            if (6 - arr1[index] > arr2[index]) return false;
            arr1[index] = 6;
            arr2[index] = diff + arr1[index];
        } else {
            if (1 + arr2[index] < arr1[index]) return false;
            arr2[index] = 1;
            arr1[index] = arr2[index] - diff;
        }
        return true;
    }
}