349. Intersection of Two Arrays

Description

The problem involves finding the intersection of two arrays, where the intersection is defined as the common elements between two arrays without duplication. We are required to return an array of these unique common elements.

Intuition

If we can efficiently track the elements in both arrays and identify which ones are present in both, we can solve the problem. Using sets, which allow for fast lookups and only store unique elements, helps reduce complexity when determining the intersection.

Approach

1. Convert both input arrays into sets. This removes duplicates and allows for quick lookup operations.
2. Iterate over the elements in one set and check if they exist in the other set.
3. If an element exists in both sets, add it to the result.
4. Return the result as a list of integers.

Complexity

Time Complexity:

O(n + m), where n is the size of the first array and m is the size of the second array. This is because we need to traverse both arrays to populate the sets, and then iterate over one of the sets to find common elements.

Space Complexity:

O(n + m), for storing the two sets and the result list.

Code

C++

class Solution {
public:
    std::vector intersection(std::vector& nums1, std::vector& nums2) {
        std::set set1(nums1.begin(), nums1.end());
        std::set set2(nums2.begin(), nums2.end());
        std::vector result;

        for (const auto& num : set2) {
            if (set1.count(num)) {
                result.push_back(num);
            }
        }
        return result;
    }
};

Python

class Solution:
    def intersection(self, nums1, nums2):
        set1 = set(nums1)
        set2 = set(nums2)
        result = []

        for num in set2:
            if num in set1:
                result.append(num)
                
        return result

Java

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set set1 = new HashSet<>();
        Set set2 = new HashSet<>();
        List result = new ArrayList<>();

        for (int num : nums1) {
            set1.add(num);
        }
        for (int num : nums2) {
            if (set1.contains(num)) {
                set2.add(num);
            }
        }

        int[] resArray = new int[set2.size()];
        int index = 0;
        for (int num : set2) {
            resArray[index++] = num;
        }
        return resArray;
    }
}

JavaScript

var intersection = function (nums1, nums2) {

    let set1 = new Set(nums1);
    let set2 = new Set(nums2);
    let result = []
    
    for (let nums of set2) {
        if (set1.has(nums)) {
            result.push(nums)
        }
    }
    return result
};