350. Intersection of Two Arrays II

Problem

Question

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must appear as many times as it shows in both arrays and you may return the result in any order.

Example 1:

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

Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4] Output: [4,9] Explanation: [9,4] is also accepted.

Constraints:

• 1 <= nums1.length, nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 1000

---

Solutions

1. 🏆 Hash Map Approach

Time Complexity: $O(n+m)$ | Space Complexity: $O(n)$

To solve the problem, we can use a dictionary to store the frequency of each number in the first array. As we iterate through the second array, we check if each number is present in the dictionary with a frequency greater than 0. If so, we add the number to the result list and decrement its frequency in the dictionary. This ensures that each number is only added to the result as many times as it appears in both arrays.

def intersect(nums1, nums2):
    memo = defaultdict(int)
    for num in nums1:
        memo[num] += 1
    
    result = []
    for num in nums2:
        if memo[num] > 0:
            result.append(num)
            memo[num] -= 1
    
    return result

2. 🍔 Overlap of Hash Maps

Time Complexity: $O(n\log n+m\log m)$ | Space Complexity: $O(n+m)$

We can also use two dictionaries and find the overlap between them. In Python, you can make aoneliner out of it.

def intersect(nums1, nums2):
	return list((Counter(nums1) & Counter(nums2)).elements())

---

3. Sorting & Two-Pointers

Time Complexity: $O(n\log n+m\log m)$ | Space Complexity: $O(min(m,n))$

Alternatively, we can sort both arrays and use a two-pointer approach. In this method, p1 points to an element in nums1, and p2 points to an element in nums2. While iterating through the sorted arrays, if the element at p1 is greater than the element at p2, increment p2. If the element at p1 is smaller, increment p1. If the elements are equal, add the element to the result list and increment both pointers. This way, you can efficiently find the common elements in both arrays.

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