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?

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.

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

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

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]

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

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!

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.