349. Intersection of Two Arrays - Explanation

Problem Link

Description

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must be unique and you may return the result in any order.

Note: The intersection of two arrays is defined as the set of elements that are present in both arrays.

Example 1:

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

Output: [2]

Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]

Output: [9,4]

Explanation: [4,9] is also accepted.

Constraints:

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

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

Intuition

The simplest approach is to check every element in the first array against every element in the second array. When we find a match, we add it to our result set. Using a set ensures we only include each common element once, even if it appears multiple times in both arrays.

Algorithm

1. Initialize an empty set res to store unique intersection elements.
2. For each element i in nums1:
   • For each element j in nums2:
     • If i == j, add i to res and break the inner loop.
3. Convert res to a list and return it.

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        res = set()
        for i in nums1:
            for j in nums2:
                if i == j:
                    res.add(i)
                    break
        return list(res)

Time & Space Complexity

• Time complexity: $O(n * m)$
• Space complexity: $O(n)$

Where $n$ is the size of the array $nums1$ and $m$ is the size of the array $nums2$.

---

2. Sorting + Two Pointers

Intuition

By sorting both arrays, we can use two pointers to efficiently find common elements. We advance the pointer pointing to the smaller element. When both pointers point to equal elements, we found an intersection. We skip duplicates to ensure each element appears only once in the result.

Algorithm

1. Sort both nums1 and nums2.
2. Initialize two pointers i and j at the start of each array.
3. While both pointers are in bounds:
   • Advance j while nums2[j] < nums1[i].
   • If nums1[i] == nums2[j], add to result.
   • Advance i, skipping any duplicates.
4. Return the result list.

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1.sort()
        nums2.sort()

        n, m = len(nums1), len(nums2)
        res, i, j = [], 0, 0

        while i < n and j < m:
            while j < m and nums2[j] < nums1[i]:
                j += 1
            if j < m:
                if nums1[i] == nums2[j]:
                    res.append(nums1[i])
                i += 1
                while i < n and nums1[i] == nums1[i - 1]:
                    i += 1

        return res

Time & Space Complexity

• Time complexity: $O(n \log n + m \log m)$
• Space complexity: $O(n)$

Where $n$ is the size of the array $nums1$ and $m$ is the size of the array $nums2$.

---

3. Hash Set

Intuition

Converting both arrays to sets removes duplicates and enables O(1) lookup. We then iterate through one set and check membership in the other. Any element present in both sets belongs to the intersection.

Algorithm

1. Convert nums1 to a set set1.
2. Convert nums2 to a set set2.
3. Iterate through set1:
   • If the element exists in set2, add it to the result.
4. Return the result list.

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        set1 = set(nums1)
        set2 = set(nums2)

        res = []
        for num in set1:
            if num in set2:
                res.append(num)
        return res

Time & Space Complexity

• Time complexity: $O(n + m)$
• Space complexity: $O(n + m)$

Where $n$ is the size of the array $nums1$ and $m$ is the size of the array $nums2$.

---

4. Hash Map

Intuition

We use a hash map to track which elements from nums1 we have seen. We mark each element with value 1. When iterating through nums2, if we find a marked element, we add it to the result and set its value to 0 to prevent duplicates.

Algorithm

1. Create a hash map seen and mark all elements in nums1 with value 1.
2. Initialize an empty result list.
3. For each element in nums2:
   • If seen[num] == 1, add num to result and set seen[num] = 0.
4. Return the result list.

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        seen = defaultdict(int)
        for num in nums1:
            seen[num] = 1

        res = []
        for num in nums2:
            if seen[num] == 1:
                seen[num] = 0
                res.append(num)
        return res

Time & Space Complexity

• Time complexity: $O(n + m)$
• Space complexity: $O(n)$

Where $n$ is the size of the array $nums1$ and $m$ is the size of the array $nums2$.

---

5. Hash Set (Optimal)

Intuition

We can improve on the two-set approach by using only one set. Store all elements from nums1 in a set, then iterate through nums2. When we find a match, add it to the result and remove it from the set to avoid duplicates.

Algorithm

1. Create a set seen from all elements in nums1.
2. Initialize an empty result list.
3. For each element in nums2:
   • If the element is in seen, add it to the result and remove it from seen.
4. Return the result list.

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        seen = set(nums1)

        res = []
        for num in nums2:
            if num in seen:
                res.append(num)
                seen.remove(num)
        return res

Time & Space Complexity

• Time complexity: $O(n + m)$
• Space complexity: $O(n)$

Where $n$ is the size of the array $nums1$ and $m$ is the size of the array $nums2$.

---

6. Built-In Functions

Intuition

Most programming languages provide built-in set intersection operations. By converting both arrays to sets and using the intersection function, we get a clean one-liner solution. The implementation details are handled by the language's standard library.

Algorithm

1. Convert nums1 to a set.
2. Convert nums2 to a set.
3. Compute the intersection of the two sets using the built-in function.
4. Convert the result to an array and return it.

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
            return list(set(nums1) & set(nums2))

Time & Space Complexity

• Time complexity: $O(n + m)$ in average case, $O(n * m)$ in worst case.
• Space complexity: $O(n + m)$

Where $n$ is the size of the array $nums1$ and $m$ is the size of the array $nums2$.

---

Common Pitfalls

Including Duplicates in the Result

The intersection should contain each common element only once, even if it appears multiple times in both arrays. For example, if nums1 = [1, 1, 2] and nums2 = [1, 1], the result should be [1], not [1, 1]. Using a set for the result or marking elements as "already added" prevents this issue.

Comparing Values Instead of Using Efficient Lookups

A brute force approach comparing every pair of elements is O(n * m), which is inefficient for large arrays. The optimal approach uses a hash set for O(1) lookups, reducing time complexity to O(n + m). Always consider converting one array to a set before checking membership.