Challenges • Asked about 1 year ago by Jake from AlgoDaily
oh my gosh
haha what's up?
Why the solution using
There are 2 inputs so we should have
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
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
O(1). Constructing the set from nums1 with the
Set constructor is
(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.