Disjoint Set & Set intersection - Python solution
Intuition & ApproachThis problem can be divited (and the conquered) into two smaller problems.IntersectionWe need an efficient way to find number of distinct in
# Intuition & Approach
This problem can be divited (and the conquered) into two smaller problems.

## Intersection

We need an efficient way to find number of distinct integers common to two arrays. The most efficient way to do this is to pre-convert all the arrays to sets and then do an intersection operation between sets.

An intersection of two sets usually takes $$O(N)$$ time since it takes $$O(1)$$ time to find whether a value is presented in a set, therefore, for $$N$$ values it will take $$O(N)$$ time.

## Relationship between nodes

We need an efficient way to find relationship between nodes of our graph (each node is represented by an array as descibed in the problem description).

This problem is usually solved by Disjoint Set/Find-Union data structure (you may check out [explore card for disjoint set](https://leetcode.com/explore/learn/card/graph/618/disjoint-set/) for more details).

The data structure (sometimes recalled as algorithm) is fairly simple. You have two methods: `find(node)` and `union(node1, node2)`. `find(node)` method finds the root of a graph that `node` is a part of. `union(node1, node2)` on the other hand unions two graphs into a bigger graph. 

To do this efficiently, we create a list of `parents` which is first filled with `-1`s representing that each node is its parent. Since we haven't started the creation of the relations yet, this is a correct representation of our graph.

For each two connected nodes in our graph, we union them by setting `parents[node2] = node1`.

After processing all the nodes we have our `parents` list with the parent node set for each node we have.

The number of remaining ``-1``s in the `parents` list is the number of connected components.

# Complexity
- Time complexity: $$O(n^2m)$$, where $$n$$ is the number of nodes (length of `properties` list), and $$m$$ is the number of elements in each property.

## Explanation

We have two nested loops to intersect each two nodes, this is $$O(n^2)$$. Then intersection operation takes $$O(m)$$ time and union operation takes $$O(1)$$ time. Therefore, the final time complexity is $$O(n^2m)$$.

- Space complexity: $$O(nm)$$, where $$n$$ is the number of nodes (length of `properties` list), and $$m$$ is the number of elements in each property.

## Explanation

We need to pre-convert all the given properties lists to sets, which use $$O(nm)$$ space. We also use $$O(n)$$ space for `parents` list. Therefore, the final space complexity is $$O(nm)$$.

# Code
```python3 []
class Solution:
    def intersect(self, a: set[int], b: set[int]) -> int:
        return len(a.intersection(b))
    
    def find(self, n: int) -> int:
        if self.parents[n] == -1:
            return n
        
        self.parents[n] = self.find(self.parents[n])

        return self.parents[n]
    
    def union(self, n1: int, n2: int) -> None:
        r1 = self.find(n1)
        r2 = self.find(n2)

        if r1 == r2:
            return
        
        self.parents[r2] = r1

    def numberOfComponents(self, properties: List[List[int]], k: int) -> int:
        n = len(properties)
        numSet = [set(p) for p in properties]

        self.parents = [-1 for _ in range(n)]

        for i in range(n-1):
            for j in range(i+1, n):
                if self.intersect(numSet[i], numSet[j]) >= k:
                    self.union(i, j)
        
        res = 0

        for p in self.parents:
            if p == -1:
                res += 1

        return res
```

![image.png](https://assets.leetcode.com/users/images/5e296fb9-bdd5-4c76-8867-7d5f34a8b2d9_1742996700.555299.png)

['Hash Table', 'Union Find', 'Graph', 'Python3']