Intersection of Two Arrays

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

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

Approach:

We want to find common elements that are in both arrays. Intersection refers to set theory and mathematics, with intersection being elements that are included in both sets.

A naive approach would be to have a nested loop, where for every element of one array we check if it exists in the second array. However in this case it would be a O(N*M) time complexity solution, since we’re going through every element of the second array for each element in the first array.

An optimization to that approach would be to sort the second array so we’d be doing binary search on the second array. This would improve our time complexity to O(N*logM) which is better but still not ideal. The sorting however gives us a better strategy.

What if we sorted both arrays? We could then look at both arrays iteratively and choosing the common elements, moving forward on the array that has the smaller number. This results in an O(N+M) approach since we look through both arrays exactly once.

Javascript Note: The code looks a bit long but don't worry, part of that is due to the callback function for the sort method. As we've often discussed, the sort method in Javascript has a default sort and takes a callback function for a custom sort. The default sort should work for numbers but unless you're familiar with exactly how it works for mixed elements for example, often it's useful to pass in a custom sort function so you know exactly what it's doing. Our sort function here is redundant, as it just sorts numerically and the input arrays are always just numbers.
var intersect = function(nums1, nums2) {
    function cb (a,b) {
        if (a<b) {
            return -1;
        }
        else {
            return 1;
        }
    }
    
    //sort
    nums1=nums1.sort(cb);
    nums2=nums2.sort(cb);
    let result=[];
    let j=0;
    for (let i=0;i<nums1.length;i++) {
        if (j>=nums2.length) {
            //we reached end of arr2
            break;
        }
        if (nums1[i]<nums2[j]) {
            //move to next i in arr1
            continue;
        }
        
        while (nums1[i]>nums2[j] && j<nums2.length) {
            j++;
        }
        if (nums1[i]===nums2[j]) {
            //console.log(i,j,"Found ",nums1[i]);
            result.push(nums1[i]);
            j++; //since we used j
            continue; //to move to next i
        }
    }
    return result;
};

Editor’s Note: This code could be improved by refactoring to use a while loop on both arrays not being exhausted and iterating through that way.