Ask A Question

Subscribe You’re not receiving notifications from this thread.

Array Intersection

Challenges • Asked about 1 year ago by Jake from AlgoDaily

Gravatar Mohamed Tarek Commented on Jul 05, 2019:

oh my gosh

Gravatar Jake from AlgoDaily Commented on Jul 05, 2019:

haha what's up?

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

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