All

# Array Intersection 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.