Intersection of Two Arrays#

Given two arrays, write a function to compute their intersection.

Example#

Solution#

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function(nums1, nums2) {
    nums1.sort((a, b) => a - b);
    nums2.sort((a, b) => a - b);
    let target = [];
    let i = 0, k = 0;
    let n1 = nums1.length, n2 = nums2.length;
    while(i<n1 && k<n2){
        if(nums1[i] < nums2[k]){
            ++i;
        }else if(nums1[i] > nums2[k]){
            ++k;
        }else{
            let last = target.length-1;
            if(target[last] !== nums1[i]) target.push(nums1[i]);
            ++i;
            ++k;
        }
    }
    return target;
};

Approach#

This is a relatively common problem. The simplest way to compute the intersection of two arrays is to traverse nums1 and, for each element, traverse nums2 to check if the element exists in nums2. This approach has a time complexity of O(mn). Here, we use the sorting and two-pointer approach. First, we sort the two arrays separately. Then, we set two pointers to traverse the arrays. We compare the elements pointed to by the two pointers. If one is smaller, we move that pointer forward. If one is larger, we move the other pointer forward. If they are equal, we first get the index of the last element in the target array. If the array is empty, it will be -1. In JavaScript, it will be undefined, and it won't be equal in the comparison below. Then, we compare whether the last element is equal to the value pointed to by the pointer. If not, we add the value to the array, which is used for deduplication. Then we move both pointers forward. After the loop ends, we return the target array.

Daily Problem#

Reference#