⚡EASY✅ AND SHORT CODE🍨|| BEATS 💯🚀||【C++/Java/Py3/JS】⌚CLEAN EXPLANATION ⌚
IntuitionWe need to construct an undirected graph where each node represents a row in the properties matrix. An edge exists between two nodes if the intersectio
# **Intuition**  
We need to construct an undirected graph where each node represents a row in the `properties` matrix. An edge exists between two nodes if the intersection of their respective lists contains at least `k` common elements. The problem then reduces to counting the number of connected components in this graph using the **Union-Find (Disjoint Set Union, DSU)** data structure.

---

# **Approach**  
1. **Initialize Union-Find (DSU) and Presence Array:**  
   - Maintain a `parent` array where each node is initially its own parent.  
   - Use a `cnt` array to store the presence of numbers in each row for quick lookups.  

2. **Mark Presence of Numbers in Each Row:**  
   - Iterate through each row and mark the numbers present in `cnt[i]`.  

3. **Check for Intersections Between Rows:**  
   - For every row `i`, compare it with all previous rows `j`.  
   - Count the number of common elements between `properties[i]` and `properties[j]`.  
   - If the common element count is **at least `k`**, merge the two rows using Union-Find.

4. **Count Connected Components:**  
   - Traverse the `parent` array and count the number of unique roots (nodes that are their own parent).  

---

# **Complexity Analysis**  
- **Preprocessing Presence Array:** `O(n m)`
- **Checking Intersections:** `O(n² . 100)`  (since we check up to 100 numbers per pair)  
- **Union-Find Operations:** `O(n . alpha(n))`, where `alpha(n)` is the inverse Ackermann function (almost constant).  
# Overall Time Complexity: O(n² + n * m)
# Overall Space Complexity: O(n)
---

# **Code**  (commented explanation)

```cpp []
class Solution {
public:
    int cnt[155][155]; // Stores presence of numbers in each row
    int par[155]; // Union-Find parent array

    // Find function with path compression
    int fin(int x) {
        if (par[x] == x) return x;
        return par[x] = fin(par[x]);
    }
    
    int numberOfComponents(vector<vector<int>>& properties, int k) {
        int n = properties.size();

        // Initialize Union-Find and presence array
        for (int i = 0; i < n; i++) {
            par[i] = i; // Initially, each node is its own parent
            memset(cnt[i], 0, sizeof(cnt[i])); // Reset presence array
            
            // Mark numbers present in the current row
            for (int num : properties[i]) cnt[i][num] = 1;

            // Compare with previous rows to check intersection count
            for (int j = 0; j < i; j++) {
                int commonCt = 0;
                // Count how many numbers appear in both rows
                for (int num = 1; num <= 100; num++) {
                    if (cnt[i][num] && cnt[j][num]) commonCt++;
                }

                // Merge components if common elements >= k
                if (commonCt >= k) par[fin(j)] = fin(i);
            }
        }

        // Count the number of connected components
        int compCt = 0;
        for (int i = 0; i < n; i++) {
            if (fin(i) == i) compCt++;
        }return compCt;
    }
};

```
```python3 []
class Solution:
    def find(self, x, parent):
        if parent[x] == x:
            return x
        parent[x] = self.find(parent[x], parent)  # Path compression
        return parent[x]

    def numberOfComponents(self, properties, k):
        n = len(properties)
        parent = [i for i in range(n)]
        cnt = [[0] * 101 for _ in range(n)]  # Presence array

        for i in range(n):
            for num in properties[i]:
                cnt[i][num] = 1

            for j in range(i):
                common_count = sum(1 for num in range(1, 101) if cnt[i][num] and cnt[j][num])
                
                if common_count >= k:
                    parent[self.find(j, parent)] = self.find(i, parent)

        return sum(1 for i in range(n) if self.find(i, parent) == i)

```
```java []
class Solution {
    find(x, parent) {
        if (parent[x] === x) return x;
        return parent[x] = this.find(parent[x], parent);
    }

    numberOfComponents(properties, k) {
        let n = properties.length;
        let parent = Array.from({ length: n }, (_, i) => i);
        let cnt = Array.from({ length: n }, () => Array(101).fill(0));

        for (let i = 0; i < n; i++) {
            for (let num of properties[i]) {
                cnt[i][num] = 1;
            }

            for (let j = 0; j < i; j++) {
                let commonCount = 0;
                for (let num = 1; num <= 100; num++) {
                    if (cnt[i][num] && cnt[j][num]) {
                        commonCount++;
                    }
                }

                if (commonCount >= k) {
                    parent[this.find(j, parent)] = this.find(i, parent);
                }
            }
        }

        return parent.filter((_, i) => this.find(i, parent) === i).length;
    }
}
```

```javascript []
/**
 * @param {number[][]} properties
 * @param {number} k
 * @return {number}
 */
var numberOfComponents = function(properties, k) {
    let n = properties.length;
    let parent = Array.from({ length: n }, (_, i) => i);
    let cnt = Array.from({ length: n }, () => Array(101).fill(0));

    // Find function with path compression
    const find = (x) => {
        if (parent[x] === x) return x;
        return parent[x] = find(parent[x]);
    };

    // Step 1: Fill presence array
    for (let i = 0; i < n; i++) {
        for (let num of properties[i]) {
            cnt[i][num] = 1;
        }

        // Step 2: Compare with previous rows
        for (let j = 0; j < i; j++) {
            let commonCount = 0;
            for (let num = 1; num <= 100; num++) {
                if (cnt[i][num] && cnt[j][num]) {
                    commonCount++;
                }
            }

            // Step 3: Union if commonCount >= k
            if (commonCount >= k) {
                parent[find(j)] = find(i);
            }
        }
    }

    // Step 4: Count connected components
    let componentCount = 0;
    for (let i = 0; i < n; i++) {
        if (find(i) === i) {
            componentCount++;
        }
    }

    return componentCount;
};

```

 
# **Code**  (withot comments)

```cpp []
class Solution {
public:
    int cnt[155][155];
    int parent[155];

    int find(int x) {
        if (parent[x] == x) return x;
        return parent[x] = find(parent[x]);
    }
    
    int numberOfComponents(vector<vector<int>>& properties, int k) {
        int n = properties.size();
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            memset(cnt[i], 0, sizeof(cnt[i]));
            for (auto v : properties[i]) cnt[i][v] = 1;

            for (int j = 0; j < i; j++) {
                int h = 0;
                for (int l = 1; l <= 100; l++) {
                    if (cnt[i][l] && cnt[j][l]) h++;
                }if (h >= k) parent[find(j)] = find(i);
            }
        }

        int res = 0;
        for (int i = 0; i < n; i++){
            if (find(i) == i) res++;
        }return res;
    }
};

```

```python3 []
class Solution:
    def find(self, x, parent):
        if parent[x] == x:
            return x
        parent[x] = self.find(parent[x], parent)
        return parent[x]

    def numberOfComponents(self, properties, k):
        n = len(properties)
        parent = [i for i in range(n)]
        cnt = [[0] * 101 for _ in range(n)]

        for i in range(n):
            for num in properties[i]:
                cnt[i][num] = 1

            for j in range(i):
                common_count = sum(1 for num in range(1, 101) if cnt[i][num] and cnt[j][num])
                
                if common_count >= k:
                    parent[self.find(j, parent)] = self.find(i, parent)

        return sum(1 for i in range(n) if self.find(i, parent) == i)
```

```java []
class Solution {
    find(x, parent) {
        if (parent[x] === x) return x;
        return parent[x] = this.find(parent[x], parent);
    }

    numberOfComponents(properties, k) {
        let n = properties.length;
        let parent = Array.from({ length: n }, (_, i) => i);
        let cnt = Array.from({ length: n }, () => Array(101).fill(0));

        for (let i = 0; i < n; i++) {
            for (let num of properties[i]) {
                cnt[i][num] = 1;
            }

            for (let j = 0; j < i; j++) {
                let commonCount = 0;
                for (let num = 1; num <= 100; num++) {
                    if (cnt[i][num] && cnt[j][num]) {
                        commonCount++;
                    }
                }

                if (commonCount >= k) {
                    parent[this.find(j, parent)] = this.find(i, parent);
                }
            }
        }

        return parent.filter((_, i) => this.find(i, parent) === i).length;
    }
}

```
```javascript []
var numberOfComponents = function(properties, k) {
    let n = properties.length;
    let parent = Array.from({ length: n }, (_, i) => i);
    let cnt = Array.from({ length: n }, () => Array(101).fill(0));

    const find = (x) => {
        if (parent[x] === x) return x;
        return parent[x] = find(parent[x]);
    };

    for (let i = 0; i < n; i++) {
        for (let num of properties[i]) {
            cnt[i][num] = 1;
        }

        for (let j = 0; j < i; j++) {
            let commonCount = 0;
            for (let num = 1; num <= 100; num++) {
                if (cnt[i][num] && cnt[j][num]) {
                    commonCount++;
                }
            }

            if (commonCount >= k) {
                parent[find(j)] = find(i);
            }
        }
    }

    let componentCount = 0;
    for (let i = 0; i < n; i++) {
        if (find(i) === i) {
            componentCount++;
        }
    }

    return componentCount;
};

```

```
✨ AN UPVOTE WILL BE APPRECIATED ^_~ ✨
```


['Union Find', 'Graph', 'Matrix', 'Prefix Sum', 'Python', 'C++', 'Java', 'Python3', 'JavaScript']