Minimum Number Of Operations To Make Arrays Similar - Leetcode Solution

Problem Statement:

Given two integer arrays nums1 and nums2 of length n, you are allowed to perform the following operation any number of times:

Swap any two elements in nums1. Swap any two elements in nums2.

The goal is to make both arrays contain the same elements. Return the minimum number of operations required to achieve this goal, or return -1 if it is impossible.

Example 1:

Input: nums1 = [1,2,3,4], nums2 = [2,1,4,5] Output: 1 Explanation: Swap nums1[3] and nums2[1].

Example 2:

Input: nums1 = [1,2,3,4], nums2 = [1,3,2,4] Output: 2 Explanation: Swap nums1[0] and nums2[1]. Swap nums1[1] and nums2[2].

Example 3:

Input: nums1 = [1,2,3,4], nums2 = [4,2,3,1] Output: -1 Explanation: It is impossible to make nums1 and nums2 the same.

Solution:

The main idea behind this solution is to find the unique elements in the input arrays and to sort them in non-decreasing order. Then we will try to match these unique elements in both arrays by swapping their positions and calculate the minimum number of operations required.

Step 1: Check if the lengths of the input arrays are the same. If not, return -1 as it is impossible to make the arrays similar.

Step 2: Find the unique elements in both arrays using a set data structure. If the intersection of the two sets is empty, return -1 as it is impossible to make the arrays similar.

Step 3: Sort the unique elements in both arrays in non-decreasing order.

Step 4: Initialize a counter to keep track of the number of operations required.

Step 5: For each unique element in the set, find its index in both arrays. If they are the same, we do not need to do anything. Otherwise, we need to swap the elements to make them the same. If it is not possible to swap the elements, return -1 as it is impossible to make the arrays similar. Increment the counter by the number of operations required to swap the elements.

Step 6: Return the counter value.

Here is the Python code for the solution:

def minOperations(nums1: List[int], nums2: List[int]) -> int: if len(nums1) != len(nums2): return -1

unique_nums1 = set(nums1)
unique_nums2 = set(nums2)

if len(unique_nums1.intersection(unique_nums2)) == 0:
    return -1

unique_nums = sorted(list(unique_nums1.union(unique_nums2)))
freq1 = [nums1.count(num) for num in unique_nums]
freq2 = [nums2.count(num) for num in unique_nums]

ops = 0
for i in range(len(unique_nums)):
    diff = abs(freq1[i] - freq2[i])
    if diff == 0:
        continue
    elif freq1[i] > freq2[i]:
        if 2*diff > sum(freq1) - sum(freq2):
            return -1
        ops += diff
    else:
        if 2*diff > sum(freq2) - sum(freq1):
            return -1
        ops += diff

return ops

Time Complexity: O(nlogn), where n is the length of the input arrays. This is due to the sorting of the unique elements in both arrays.

Space Complexity: O(n), where n is the length of the input arrays. This is due to the use of set and list data structures to store the unique elements.

1