Intersection of Two Arrays

How it works

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.

Steps

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.

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.

Things to watch for

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.

from typing import List

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

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        set<int> set1(nums1.begin(), nums1.end()), set2(nums2.begin(), nums2.end());
        vector<int> res;
        set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(), back_inserter(res));
        return res;
    }
};