Brute Force

We'll start off slowly, by using the smallest sample inputs possible to examine the make-up of the problem. We know we'll need a result array to return, so hold that in mind:

1const results = [];

Let's say we need to find the intersection of two arrays: [1] and [1]. In this case, we know that the output is also [1]-- it's rather simple, because we just need to do a straight comparison of 1 and 1. We go through the first [1], see the 1, and locate it in the second array. Because they're the same, we just return a result with that match.

So we need to expand beyond this. Let's say the two inputs are modified to [1] and [2]. Well, when we compare the two single elements, we know that they're not the same. We thus don't need to do anything with result.

As this continues beyond one array element, we can continue this process of checking if each element in the first array exists in the second.

So, we can loop through the first array, and at each iteration, check whether that element exists in the second array. We can check the existence of elements in the second array using nums2.indexOf(num) !== -1. But after this, we need to make sure that the returning array has unique elements. We can easily do this by hashing technique. A hash Object will suffice to ensure uniqueness. This works because object keys must be unique.

1const first = [4, 9, 5];
2const second = [9, 4, 9, 8, 4];
3
4function intersection(nums1, nums2) {
5	let intersection = {};
6
7	for (const num of nums1) if (nums2.indexOf(num) !== -1) intersection[num] = 1;
8
9	return Object.keys(intersection).map((val) => parseInt(val));
10}

A much simpler way of doing the same thing using the includes method is given below.

But the problem with this implementation is its inefficiency. For example, in the below js implementation, it takes O(n*m) where n and m are the lengths of the arrays. It first runs a loop using firstArray.filter method, and then at each iteration, it calls secondArray.includes(el) which is linear in time.

xxxxxxxxxx

const firstArray = [4, 9, 5];

const secondArray = [9, 4, 9, 8, 4];

​

let intersection = firstArray.filter((el) => {

  return secondArray.includes(el);

});