Here is the interview question prompt, presented for reference.

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.

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:

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

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

And here's another one:

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

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

You can see the full challenge with visuals at this link.

**Challenges**
• Asked over 1 year ago by Jake from AlgoDaily

haha what's up?

oh my gosh

Why the solution using `Set`

is `O(n)`

?

There are 2 inputs so we should have `n`

and `m`

, no?

Assume that `n`

is the size of *nums1*, and `m`

is *nums2*. We traverse nums2 with `filter()`

and in every iteration we traverse nums1 with `has()`

. So shouldn't it be `O(m*n)`

?

Correct me if I'm wrong, but I think I've found the answer:

*"Set objects must be implemented using [mechanisms] that, on average, provide access times that are sublinear on the number of elements in the collection"*

If I understand correctly, implementing `Set`

with *Disjoint Sets* data structure, for example, the complexity of `has()`

is `O(1)`

. Constructing the set from *nums1* with the `Set`

constructor is `O(n)`

.

(Look here for more details).

So we have *m* operations of `O(1)`

after constructing the set from *nums1*. That gives us complexity of `O(n+m)`

, which is roughly `O(n)`

assuming that *n* is the larger input.

oh my gosh

haha what's up?

`Set`

is `O(n)`

?

There are 2 inputs so we should have `n`

and `m`

, no?

Assume that `n`

is the size of *nums1*, and `m`

is* nums2*. We traverse nums2 with `filter()`

and in every iteration we traverse nums1 with `has()`

. So shouldn't it be `O(m*n)`

?

*"Set objects must be implemented using [mechanisms] that, on average, provide access times that are sublinear on the number of elements in the collection"*

If I understand correctly, implementing `Set`

with *Disjoint Sets* data structure, for example, the complexity of `has()`

is `O(1)`

. Constructing the set from *nums1* with the `Set`

constructor is `O(n)`

.

(Look here for more details).

So we have *m* operations of `O(1)`

after constructing the set from *nums1*. That gives us complexity of `O(n+m)`

, which is roughly `O(n)`

assuming that *n* is the larger input.

can someone please explain what the (n) => set.has(n) part does?

same for the [...filteredSet] i.e. the '...'?

That line consist of two parts. The filter returns a new array after a certain condition is passed. In this case >set.has(n). The has() method of a set returns true if a certain element is present in a set

Java & C++ solution, please?

[deleted]

[deleted]

Hi, the Java solution is already present, please change your language to Java to see. C++ will be coming soon!

It's a callback function passed to the Array.prototype.filter( ) method that is called sequentially on each element in the nums2 array. The n is a temp variable that holds each element in turn and is passed to Set.prototype.has( ) that returns a Boolean: true if the set contains n and false if not.

a python solution using dictionary:

def intersection (list1, list2):

# convert lists to dict

dict1 = {}

dict2 = {}

result = []

for item in list1:

dict1[item] = dict1.get(item, 0) + 1

for item in list2:

dict2[item] = dict2.get(item, 0) + 1

for key in dict1.keys():

if dict2.get(key, 0) > 0:

result.append(key)

return result

but the `(nums2.indexOf(num)`

is taking O(m), m = len(nums2) right?

and also the outer loop is going till len(nums1).

isn't it O(n*m)?

A python solution using a set since we are looking for values in both arrays but not how many times the occur .

1. We will put all the numbers from nums1 array inside the set ( Since sets only contain unique values,any duplicate will not be added)

2. We loop through the second array (nums2) and check the set (the lookup time for set is O(1) ), if it contains the current value in nums2 , we add it to the results array and delete it from the set.

3. Return the result array

The time complexity for this is O(n) . We have two seperate loops one for nums1 and the other for nums2

```

def intersection(nums1, nums2):

# fill this in

ans=set()

result=[]

for num in nums1:

ans.add(num)

for num in nums2:

if num in ans:

result.append(num)

ans.remove(num)

return result