Community

Start a Thread


Notifications
Subscribe You’re not receiving notifications from this thread.

Array Intersection

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.

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)).

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

Challenges • Asked about 2 years ago by Jake from AlgoDaily

Jake from AlgoDaily Commented on Jul 01, 2019:

haha what's up?

Mohamed Tarek Commented on Jul 01, 2019:

oh my gosh

Leon Commented on Jul 04, 2019:

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)?

Leon Commented on Jul 04, 2019:

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.

Mohamed Tarek Commented on Jul 05, 2019:

oh my gosh

Jake from AlgoDaily Commented on Jul 05, 2019:

haha what's up?

Leon Commented on Jul 05, 2019:

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)?

Leon Commented on Jul 05, 2019:

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.

Anonymous Commented on Jul 28, 2019:

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

Anonymous Commented on Jul 28, 2019:

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

Anonymous Commented on Aug 16, 2019:

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

Anonymous Commented on Jul 06, 2020:

Java & C++ solution, please?

Anonymous Commented on Jul 06, 2020:

[deleted]

Anonymous Commented on Jul 06, 2020:

[deleted]

Jake from AlgoDaily Commented on Jul 06, 2020:

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

tomalgo Commented on Jul 09, 2020:

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.

abrar Commented on Jul 24, 2020:

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

abrar Commented on Jul 24, 2020:

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)?

bsanneh Commented on Jan 08, 2021:

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

George Commented on Feb 12, 2021:

Hi all! Thank you for your work guys!

  1. I would like to make some comments on testing. JUnit assertEquals expects parameters in the following order: 1. Expected 2. Actual

In your tests you put it vice versa which is not correct.

  1. Also in the arrayIntersection problem in the proposed tests you compare arrays via assertEquals which is not correct as it compares arrays by reference (and they cannot be identical).

You have to use assertArrayEquals().

Thanks!

Rahat Zaman Commented on Feb 16, 2021:

Hi all, this is Rahat from AlgoDaily. Thank you all for pointing out the limitations in the lesson. I am now going to reference each points here.

@Leon, you are right in your answer! The complexity of almost all single operations (insertion, deletion, lookup) in most modern programming languages are O(1). And building a set out of array takes O(n) (n=length of array).

And the final time complexity of this problem will be O(n+m).

And, [...filteredSet] is a spread operator. It can be used to convert a set to an array.

(n) => set.has(n): This part is actually a lambda function. You can think this of a "portable" function, which takes a parameter n, and returns boolean of whether n is in the set or not.

@abrar, You are right. That solution was actually O(n*m) and we fixed it now.

@George, We will update the assertions soon. But, here assertArrayEquals will also not work. Because there is no instruction given on how the intersection array should be ordered, we much check the equality without the order. We will update this soon.

Also, we will be adding multiple languages for all problems in the platform. We are working on it and hope it will be added soon.

Thanks to everyone once again.