12-line union find + bit masks, beats 99.65%
Complexity
Time complexity: O(m∗n)
Space complexity: O(n)
Submissionhttps://leetcode.com/problems/properties-graph/submissions/1591932651/Code
# Complexity
- Time complexity: $$O(m*n)$$
- Space complexity: $$O(n)$$

# Submission
https://leetcode.com/problems/properties-graph/submissions/1591932651/

# Code
```python3 []
class Solution:
    def numberOfComponents(self, properties: List[List[int]], k: int) -> int:
        # Union find: parents + parent getter with path compression
        parent = list(range(len(properties)))
        def get_parent(node):
            res = node
            while parent[res] != res:
                res = parent[res]
            parent[node] = res
            return res

        # Turn arrays into bit masks due to small range of values
        mask = [reduce(or_, [1 << o for o in pr]) for pr in properties]

        # Find disjoint sets using the union find algorithm
        for i, j in combinations(range(len(mask)), 2):
            if (mask[i] & mask[j]).bit_count() >= k:
                parent[get_parent(i)] = get_parent(j)

        # Return the number of root nodes in the parent graph
        return sum(i == parent[i] for i in range(len(parent)))
```
['Python3']