[Go, Python3] 0ms 9.26MB Fastest Go solution using Union Find and BitMask with explanations
IntuitionWe need to count how many connected components exist in the graph, and the Union-Find (Disjoint Set Union) algorithm is a perfect fit for this type of
![image.png](https://assets.leetcode.com/users/images/baf537e9-e2f1-464c-9667-6f1b85d846c6_1742723236.7539585.png)

# Intuition
We need to count how many connected components exist in the graph, and the **Union-Find** (Disjoint Set Union) algorithm is a perfect fit for this type of problem. Which is special about this problem is that we don't have neither adjacency list nor list of edges given to us as an input. Instead we are gives list of sets (although they are arrays, but problem states that "*...that returns the **number of distinct integers**...*" so we can simply ignore it and threat them as sets). We know the there's an edge between two vertices if they share **at least `k` common integers** (set intersection).
# Approach
1. Representing Sets Efficiently with Bitsets
Instead of using an array of maps `sets := []map[int]struct{}`, (which is relatively slow in Go), we use a **bitmask** representation. Given the constraint `(1 <= properties[i][j] <= 100)` we know the maximum integer is `100`. We need at least **100 slots**, which can be efficiently stored using **two** **`uint64` values** (providing 128 bits in total).
or example, if a vertex is represented by the set `[1, 4, 5, 9]`, we encode it as a bitmask where the corresponding bit positions are set to `1`.
 `high = 000...000,
low = ...100011001`
This encoding allows us to efficiently check intersections using bitwise operations.
We also initialize the `parent` and `rank` arrays for the Union-Find.

2. Building the Adjacency List
We construct the adjacency list by comparing every pair of vertices. If two vertices share **at least `k` common elements**, we add an edge between them. To check for common elements, we use the bitwise AND operation between the corresponding low and high parts of their `BitSet` representation and count the number of `1` bits using the `bits.OnesCount64` function.

3. Union-Find with Path Compression
We perform a classic Union-Find algorithm with path compression for efficient merging of components. Each time we successfully unite two components, we decrement the count of components n. By the end of this process, n will represent the number of connected components.

# Complexity
- Time complexity: $$O(n^2)$$
Constructing the bitsets: $$O(n \times m) $$ where n is the number of vertices and m is the maximum length of the sets (in this case, at most 100).
Building the adjacency list: $$O(n^2)$$ since we compare all pairs of vertices.
Union-Find operations: $$O(n \times \alpha(n) )$$ where $$\alpha(n)$$ is the inverse Ackermann function (amortized constant time).

- Space complexity: $$O(n)$$
Bitsets: $$O(n)$$ (two uint64 per vertex).
Union-Find arrays: $$O(n)$$ (parent and rank arrays).
Adjacency list: $$O(E)$$ Where $$E$$ is the amound of edges.


# Code
```golang []
type BitSet struct {
	low, high uint64
}

func numberOfComponents(properties [][]int, k int) (r int) {
	n := len(properties)
    // 1. Initialize and fill main data structures
	sets := make([]BitSet, n)
	parent := make([]int, n)
	rank := make([]int, n)
	for idx, arr := range properties {
		parent[idx] = idx
		rank[idx] = 1

        // use BitSet as bool array setting bit 1 if number is in set
		for _, v := range arr {
			if v < 64 {sets[idx].low |= (1 << v)
			} else {sets[idx].high |= (1 << (v - 64))}
		}
	}

    // 2. Build adjacency list by adding edges for all sets with at least k common integers
	adjList := make([][]int, n)
	for idxI, setI := range sets {
		for idxJ := idxI + 1; idxJ < n; idxJ++ {
			setJ := sets[idxJ]
            // check how many bits which are set to 1 are shared which is basically equivalent to set intersection
			if bits.OnesCount64(setI.low&setJ.low) + bits.OnesCount64(setI.high&setJ.high) >= k {
				adjList[idxI] = append(adjList[idxI], idxJ)}
		}
	}

    // 3. Union find functions declaration
	find := func(p int) int {
		for p != parent[p] {
			parent[p] = parent[parent[p]]
			p = parent[p]
		}
		return p
	}

	union := func(n1, n2 int) {
		a, b := find(n1), find(n2)

		if a == b {return}

		if rank[a] > rank[b] {
			rank[a] += rank[b]
			parent[b] = a
			n--
		} else {
			rank[b] += rank[a]
			parent[a] = b
			n--
		}
	}

    // Perform union on all edges we constructed previously
	for a, edges := range adjList {
		for _, b := range edges {union(a, b)}
	}

	return n

}
```

I also provide simpler python code which uses simple sets for comparison, is some parts in Go look confusing. It's much slower, but still fast among python solution 
![image.png](https://assets.leetcode.com/users/images/7a97a037-3e8c-4314-b4a9-2c14f128950a_1742723182.985351.png)

```python
class Solution:
    def numberOfComponents(self, properties: List[List[int]], k: int) -> int:
        properties = [set(i) for i in properties]
        n = len(properties)
        adjList = defaultdict(list)
        for idx_i, i in enumerate(properties):
            for idx_j, j in enumerate(islice(properties, (_from:=idx_i+1), None), start=_from):
                if len(i.intersection(j)) >= k:
                    adjList[idx_i].append(idx_j)
    
        parent = list(range(n))
        rank = [1] * n
    
        def find(p):
            while p != parent[p]:
                parent[p] = parent[parent[p]]
                p = parent[p]
            return p
    
        def union(n1, n2):
            a, b = find(n1), find(n2)
    
            if a == b:
                return
    
            if rank[a] > rank[b]:
                rank[a] += rank[b]
                parent[b] = a
                self.components -= 1
            else:
                rank[b] += rank[a]
                parent[a] = b
                self.components -= 1
            
        self.components = n
        for a, v in adjList.items():
            for b in v:
                union(a, b)
            
        return self.components
```
['Bit Manipulation', 'Union Find', 'Bitmask', 'Go', 'Python3']