Javascript Interview and Prep: Intersection of unsorted arrays

Prompt: Given two arrays, find the intersection (items occur in both arrays)

1. arrays are not sorted, and might have duplicates.
2. you can modify the arrays
3. you can return the items in any order, but without duplicates.

What is the time & space complexity of your approach?

Answer 1: O(n) complexity — preferred answer

• Here we convert the arrays into a Set. The reason is that it will remove all duplicate values in the array. Once the 2 arrays have duplicates removed, then we will map through the array (which will create the O(n) complexity). The method to use to check if the value is in the set is has(). Or another way is to convert set “b” into an array by using […b].includes().

/**
 * @param {any[]} arr1
 * @param {any[]} arr2
 * @returns {any[]}
 */
function getIntersection(arr1, arr2) {
  let a = new Set(arr1);
  let b = new Set(arr2);

  [...a].filter((each, eachIndex) => {
    if (b.has(each)){
      resArr.push(each);
    }
  })
  return resArr;

getIntersection([1,2,3,3,3,3], [3,4,5,5,5]); //3
getIntersection([1,2,3], [3,2,1]); //1,2,3

Answer 2: O(n²) complexity — not preferred answer

• This method is not preferred because we have to map through 2 nested arrays causing O(n²) time.

/**
 * @param {any[]} arr1
 * @param {any[]} arr2
 * @returns {any[]}
 */
function getIntersection(arr1, arr2) {
  // your code here
  const resArr = [];
  arr1.map((each, eachIndex) => {
    arr2.map((each2, each2Index) => {
      if (each == each2 && !resArr.includes(each)){
        resArr.push(each);
      }
    })
  });
  return resArr;
}

getIntersection([1,2,3,3,3,3], [3,4,5]); //3
getIntersection([1,2,3], [3,2,1]); //1,2,3