Python beats 99%. Union Find + Bit Set
IntuitionWhen a problem asks for the number of connected components, union-find should be at the top of your list for things to try. This problem is asking you
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
When a problem asks for the number of connected components, union-find should be at the top of your list for things to try. This problem is asking you to build a graph where each node is a set of integers and there is an edge between every two nodes whose intersection is at least size k.

Simply create sets from each list and intersect them to see whether they are connected. If they are union the components together.

# Approach
<!-- Describe your approach to solving the problem. -->
First note that the numbers only go up to 100. We can use bit sets to represent the sets. Normal Python ints can be used as bit sets for relatively small numbers. Note that doing bit operations on really large numbers will be very slow, so consider implementing bit sets as a class when needed. For only 100 bits, normal ints will be fine.

Convert each list of ints into a bit set. For each bit set, check if the intersection has at least k bits set. If so, union the indices. This step is where you can save a lot of time by using the built-in bit_count() method for ints. I get around 50 ms using this method and around 300 ms using the standard hamming weight algorithm which I left commented. I tried passing k and returning as soon as `c >= k`, but that was about the same. The bit_count method is implemented in c in cpython, so it runs a lot faster than a python implementation.

Finally find the number of connected components by counting the number of unique parents.


# Complexity
$n$ is the number of properties, $m$ is the size of each property, $l$ is the largest value contained in a property.
- Time complexity: $$O(n * m * l)$$
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
The union-find complexity is dominated by the intersect complexity, so the reverse Ackermann function does not appear in the time complexity.

- Space complexity: $$O(n * l)$$
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
The number of bits used in each bit set scales with the largest value of all properties, albeit with a small constant factor.

# Code
```python3 []
class Solution:
    def numberOfComponents(self, properties: List[List[int]], k: int) -> int:
        n = len(properties)
        self.parents = [i for i in range(n)]

        properties = [reduce(lambda x, y: x | (1 << y-1), prop, 0) for prop in properties]
        
        for i in range(n-1):
            for j in range(i+1, n):
                if self.intersect(properties[i], properties[j]) >= k:
                    self.union(i, j)

        unique_parents = {self.find(i) for i in range(n)}
        return len(unique_parents)

    def intersect(self, a, b):
        return (a & b).bit_count()
        # n = a & b
        # c = 0
        # while n:
        #     n &= n-1
        #     c += 1
        # return c

    def find(self, x):
        if x != self.parents[x]:
            self.parents[x] = self.find(self.parents[x])
        return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        self.parents[x] = y
```

![image.png](https://assets.leetcode.com/users/images/3dc97673-b8a2-498b-86f6-7dd50b7302e1_1742978394.095297.png)


['Bit Manipulation', 'Union Find', 'Python', 'Python3']