Leetcode – Intersection of Two Arrays II Solution in Python

Spread the love

In this article, we will delve into solving the “Intersection of Two Arrays II” problem available on LeetCode.

Understanding the Problem Statement

The “Intersection of Two Arrays II” problem on LeetCode requires you to find the intersection of two arrays, where each element in the output should appear as many times as it shows in both arrays.

Example:

Input: nums1 = [1,2,2,1], nums2 = [2,2]

Output: [2, 2]

This differs from the “Intersection of Two Arrays” problem where the output should only contain unique elements.

Exploring Different Approaches

Brute Force Method

The simplest approach is to use two nested loops. For each element in the first array, search for the same element in the second array. This approach is not efficient, especially for large datasets.

def intersect(nums1, nums2):
    result = []
    for num in nums1:
        if num in nums2:
            result.append(num)
            nums2.remove(num)
    return result

Using Hash Maps

An efficient approach involves using hash maps. Store the count of each element in the first array in a hash map. Then, iterate through the second array, and if an element is found in the hash map, decrease its count and add it to the result list.

def intersect(nums1, nums2):
    counter = {}
    result = []
    
    for num in nums1:
        counter[num] = counter.get(num, 0) + 1
        
    for num in nums2:
        if num in counter and counter[num] > 0:
            result.append(num)
            counter[num] -= 1
            
    return result

Sorting and Two Pointers

Similar to the Intersection of Two Arrays problem, if the arrays are sorted or sorting is not a concern, the two-pointer technique can be applied. However, in this case, you have to handle duplicates by checking the count of each element.

def intersect(nums1, nums2):
    nums1.sort()
    nums2.sort()
    
    result = []
    i, j = 0, 0
    
    while i < len(nums1) and j < len(nums2):
        if nums1[i] < nums2[j]:
            i += 1
        elif nums1[i] > nums2[j]:
            j += 1
        else:
            result.append(nums1[i])
            i += 1
            j += 1
            
    return result

Time and Space Complexity Analysis

  • Brute Force: Time complexity is O(n * m) and space complexity is O(min(n, m)).
  • Using Hash Maps: Time complexity is O(n + m) and space complexity is O(min(n, m)).
  • Sorting and Two Pointers: Time complexity is O(n log n + m log m) and space complexity is O(min(n, m)).

Optimization Techniques

The most efficient approach among the three is using hash maps. However, in scenarios where the input arrays are already sorted, the two-pointer technique can be a viable option without the extra space requirement.

Conclusion

The “Intersection of Two Arrays II” problem allows us to explore various algorithmic techniques. Understanding the differences in handling duplicates between this problem and its variant is key. The ability to reason through and choose the most effective approach for a given scenario is an invaluable skill for programming interviews and real-world problem-solving.

Leave a Reply