Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

3809. Properties Graph

My accepted Python solution to LeetCode problem 3809, Properties Graph, running in 218ms.

  • Difficulty: Medium
  • Python
  • Runtime 218ms
  • Memory 18.6MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

Python

Accepted on LeetCode — runtime 218ms, memory 18.6MB, accepted 2025-12-30.

python
class Solution:
    def numberOfComponents(self, properties: List[List[int]], k: int) -> int:
        n = len(properties)
        # Convert to sets for intersection
        prop_sets = [set(p) for p in properties]
        
        # Union-Find
        parent = list(range(n))
        
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
        
        def union(x, y):
            px, py = find(x), find(y)
            if px != py:
                parent[px] = py
        
        # Connect nodes with intersection >= k
        for i in range(n):
            for j in range(i + 1, n):
                if len(prop_sets[i] & prop_sets[j]) >= k:
                    union(i, j)
        
        # Count unique roots
        return len(set(find(i) for i in range(n)))

Source