LeetCode — 349. Intersection of Two Arrays

In today’s blog post, we’re going to look at a simple yet efficient way to find the common elements between two arrays in JavaScript. The core idea of our approach revolves around the utilization of the Set data structure, known for its unique ability to store distinct values.

Here’s an overview of our method

The central concept is to leverage a Set to keep track of all the unique elements from one of the arrays. We then iterate through the second array, checking whether each of its elements is present in the Set. If an element from the second array is found in the Set, it signifies that the element is common to both arrays, and thus, it becomes a part of our intersection set.

This method is straightforward yet powerful due to the inherent properties of a Set in JavaScript. The uniqueness and quick lookup features of a Set make it an ideal choice for this kind of operation.

Now, let’s dive into the complexities involved:

Time Complexity

• O(n + m): Where n is the length of the first array, and m is the length of the second. The time complexity is linear since we iterate through both arrays entirely. The operations within each iteration, like adding elements to a Set or checking for an element's presence, are constant time operations.

Space Complexity

• O(n): We need additional space to store the unique elements from one of the arrays, which in the worst case, could be as large as the array itself. Hence, the space complexity is proportional to the size of the larger array.

JavaScript Version

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function (nums1, nums2) {
    const allNumbers = new Set();
    const intersectNumbers = new Set();

    // compare which one is longer
    if (nums1.length < nums2.length) {
        [nums1, nums2] = [nums2, nums1];
    }

    // loop nums1 get all the unique num
    for (let item1 of nums1) {
        allNumbers.add(item1);
    }

    for (let item2 of nums2) {
        if (allNumbers.has(item2)) {
            intersectNumbers.add(item2);
        }
    }

    return Array.from(intersectNumbers);
};

Java Version

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        if(nums1 == null || nums1.length == 0 || nums2==null || nums2.length==0 ) 
            return new int[0];

            if(nums1.length < nums2.length) {
                int[] tempNum = nums1;
                nums1 = nums2;
                nums2 = tempNum;
            }

            Set<Integer> allNums = new HashSet<>();
            Set<Integer> resSet = new HashSet<>();

            for(int num1 : nums1) {
                allNums.add(num1);
            }

            for(int num2 : nums2) {
                if(allNums.contains(num2)) {
                    resSet.add(num2);
                }
            }

            return resSet.stream().mapToInt(x -> x).toArray();
    }
}