Array Intersection

As we ease our way into the course, we'll want to start with the basic data structures and their operations. However, don't be fooled how fundamental these things are!

Interviewers will often test you on things that are deceptively easy. We saw this in Reverse a String, and will see more in future challenges. But sometimes you might get tested on a concept that, while a bit trivial, is really useful in day to day software engineering.

One of those things is array manipulation, or basically doing things to an array that creates some kind of transformation.

Prompt

Can you write a function that takes two arrays as inputs and returns to us their intersection? We can call the method intersection. Let's return the intersection of the two inputs in the form of an array. As a reminder, the definition of an intersection of two sets A and B is the set containing all elements of A that also belong to B (or equivalently, all elements of B that also belong to A).

Note that all elements in the final result should be unique. Here's one example:

const nums1 = [1, 2, 2, 1];
const nums2 = [2, 2];

intersection(nums1, nums2);
// [2]

And here's another one:

const nums1 = [4,9,5];
const nums2 = [9,4,9,8,4];

intersection(nums1, nums2);
// [9, 4]

Constraints

• Length of the array <= 100000
• The values in the array will be in the range -1000000000 and 1000000000
• Expected time complexity: O(n+m) where n and m are the lengths of the array.
• Expected space complexity: O(max(n,m)).

```js
function intersection(nums1, nums2) {
  // fill this in
  return [];
}
```

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:

const results = [];

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.

const first = [4, 9, 5];
const second = [9, 4, 9, 8, 4];

function intersection(nums1, nums2) {
    let intersection = {};

    for (const num of nums1) if (nums2.indexOf(num) !== -1) intersection[num] = 1;

    return Object.keys(intersection).map((val) => parseInt(val));
}

first = [4, 9, 5]
second = [9, 4, 9, 8, 4]

def intersection(nums1, nums2):
  intersection = {}

  for num in nums1:
    if num in nums2:
      intersection[num] = 1

  return list(intersection.keys())

print(intersection(first, second))

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.

```js
const firstArray = [4, 9, 5];
const secondArray = [9, 4, 9, 8, 4];

let intersection = firstArray.filter((el) => {
  return secondArray.includes(el);
});
```
```py
first = [4, 9, 5]
second = [9, 4, 9, 8, 4]

def intersection(nums1, nums2):
  return list(filter(lambda num: num in nums2, nums1))

print(intersection(first, second))
```
```java
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

public class Main {
  public static void main(String[] args) {
    List<Integer> first = Arrays.asList(4, 9, 5);
    List<Integer> second = Arrays.asList(9, 4, 9, 8, 4);

    List<Integer> intersection = first.stream()
      .filter(num -> second.contains(num))
      .collect(Collectors.toList());

    System.out.println(intersection);
  }
}
```

The concept of intersection is from set theory, so this problem is really simple if we just use Sets! In mathematics, the intersection of two sets A and B is the set that contains all elements of A that also belong to B.

Sets are an object type in most languages that allow you to store unique values of most primitives. The strength of set is that implementation of unordered set in most programming languages only takes O(1) worst time complexity for checking the existence of an element. So, we can replace the secondArray.includes(el) part of previous js code with a set operation!

If we transform our input arrays into sets, we can make use of the filter method, and apply it to one of the sets-- filtering out anything not in the other set.

```js
const first = [4, 9, 5];
const second = [9, 4, 9, 8, 4];

function intersection(nums1, nums2) {
  const set = new Set(nums1);
  const filteredSet = new Set(nums2.filter((n) => set.has(n)));
	return [ ...filteredSet ];
}
```
```py
first = [4, 9, 5]
second = [9, 4, 9, 8, 4]

def intersection(nums1, nums2):
    s1 = set(nums1)
    s2 = set(nums2)
    return s1.intersection(s2)

print(intersection(first, second))
```

The creation of a set from an array of n elements takes O(n) time complexity. Let us think that the first array is of length n and the second array is of length m.

Then the final time complexity of the above implementation would be O(m+n). Let us explain this step-by-step:

1. We create a set from the first array: O(n).
2. We traverse through the second array with filter method which takes O(m). In this traversal process, we check if that element exists in the set from the first array which takes O(1).
3. Finally we create the resulting array from the filtered second array which takes O(m) worst time. Remember, although we may return an array, it is crucial to building a set first. The reason is to remove duplicates from the filter of the second array.

So, the final time complexity is O(n + m + m) = O(m+n).

This problem will help you to get experience on where to use the set even if it is not mentioned in the problem statement. It might be helpful to use the Set if you encounter a similar problem during your interview. This is because it demonstrates knowledge of a commonly used data structure and a background in mathematics.

One Pager Cheat Sheet

• We need to write a function called intersection which takes two arrays as inputs and returns their intersection as a unique set of values.
• We can brute force the intersection of two arrays by looping through the first array, checking if each element exists in the second array, and then adding the element to an object to ensure uniqueness of the items in the result array.
• We can make use of Sets and the filter method to find the intersection of two arrays in O(1) time complexity.
• The creation of a set from an array of n elements and checking for its existence in a second array of m elements takes O(m+n) time complexity.
• The problem helps you learn when to use the Set data structure, thereby emphasizing mathematics and interview preparation.