# Properties Graph
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/properties-graph)
Canonical: https://scaleengineer.com/dsa/problems/properties-graph
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search), [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** Array, Hash Table, Graph
---
## Problem
You are given a 2D integer array `properties` having dimensions `n x m` and an integer `k`.

Define a function `intersect(a, b)` that returns the **number of distinct integers** common to both arrays `a` and `b`.

Construct an **undirected** graph where each index `i` corresponds to `properties[i]`. There is an edge between node `i` and node `j` if and only if `intersect(properties[i], properties[j]) >= k`, where `i` and `j` are in the range `[0, n - 1]` and `i != j`.

Return the number of **connected components** in the resulting graph.

**Example 1:**

**Input:** properties = \[\[1,2\],\[1,1\],\[3,4\],\[4,5\],\[5,6\],\[7,7\]\], k = 1

**Output:** 3

**Explanation:**

The graph formed has 3 connected components:

![](https://assets.glich.co/dsa/properties-graph/image0.png)

**Example 2:**

**Input:** properties = \[\[1,2,3\],\[2,3,4\],\[4,3,5\]\], k = 2

**Output:** 1

**Explanation:**

The graph formed has 1 connected component:

![](https://assets.glich.co/dsa/properties-graph/image1.png)

**Example 3:**

**Input:** properties = \[\[1,1\],\[1,1\]\], k = 2

**Output:** 2

**Explanation:**

`intersect(properties[0], properties[1]) = 1`, which is less than `k`. This means there is no edge between `properties[0]` and `properties[1]` in the graph.

**Constraints:**

* `1 <= n == properties.length <= 100`
* `1 <= m == properties[i].length <= 100`
* `1 <= properties[i][j] <= 100`
* `1 <= k <= m`

# Approaches
## Brute-Force Graph Construction with DFS/BFS
This is a straightforward, brute-force approach. The core idea is to first explicitly construct the graph based on the problem's definition and then use a standard graph traversal algorithm to count the connected components.
**Time:** O(n^2 * m) - There are `O(n^2)` pairs of properties to check. For each pair, the `intersect` function takes `O(m)` time to create a HashSet and iterate. The final graph traversal (DFS/BFS) takes `O(n + E)`, where `E` is the number of edges (at most `O(n^2)`), which is dominated by the graph construction time. · **Space:** O(n^2) - In the worst-case scenario (a complete graph), the adjacency list will store `O(n^2)` edges. The `visited` array and recursion stack for DFS take `O(n)` space.
**Pros:** Easy to understand and implement.; Follows a standard pattern for graph problems: build then traverse.
**Cons:** The space complexity of `O(n^2)` is high and can be a bottleneck for larger `n`.; Building the full adjacency list can be memory-intensive if the graph is dense.
### Explanation
The process involves two main phases. First, we build the graph. We iterate through all unique pairs of properties. For each pair, we compute their intersection size. If it meets the threshold `k`, we add an edge to an adjacency list. To compute the intersection efficiently, we can use a `HashSet` to store the elements of one property array, allowing for quick checks of common elements. 

Once the adjacency list is fully populated, the second phase begins: counting the components. We use a `visited` array and loop through all nodes. If we find an unvisited node, we've discovered a new component. We increment our component counter and start a traversal (e.g., DFS) from that node to mark all reachable nodes as visited. This ensures we count each component only once.

```java
import java.util.*;

class Solution {
    public int countConnectedComponents(int[][] properties, int k) {
        int n = properties.length;
        List<Integer>[] adj = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
        }

        // 1. Build the graph
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (intersect(properties[i], properties[j]) >= k) {
                    adj[i].add(j);
                    adj[j].add(i);
                }
            }
        }

        // 2. Count connected components using DFS
        boolean[] visited = new boolean[n];
        int componentCount = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                componentCount++;
                dfs(i, adj, visited);
            }
        }

        return componentCount;
    }

    private int intersect(int[] a, int[] b) {
        Set<Integer> setA = new HashSet<>();
        for (int val : a) {
            setA.add(val);
        }

        Set<Integer> common = new HashSet<>();
        for (int val : b) {
            if (setA.contains(val)) {
                common.add(val);
            }
        }
        return common.size();
    }

    private void dfs(int u, List<Integer>[] adj, boolean[] visited) {
        visited[u] = true;
        for (int v : adj[u]) {
            if (!visited[v]) {
                dfs(v, adj, visited);
            }
        }
    }
}
```
### Algorithm
- **Graph Representation**: Use an adjacency list, `List<Integer>[] adj`, to represent the graph, where `adj[i]` stores all neighbors of node `i`.
- **Graph Construction**:
  - Iterate through every possible pair of properties `(properties[i], properties[j])` where `i < j`.
  - For each pair, calculate the number of common distinct elements. A simple way is to convert `properties[i]` into a `HashSet` for O(1) average time lookups.
  - Then, iterate through the unique elements of `properties[j]` and count how many are present in the set of `properties[i]`.
  - If the count of common elements is greater than or equal to `k`, add an undirected edge between nodes `i` and `j` in the adjacency list.
- **Count Components**:
  - Initialize a `visited` boolean array of size `n` to keep track of visited nodes.
  - Initialize a counter for connected components, `componentCount`, to zero.
  - Iterate through each node from `0` to `n-1`.
  - If a node `i` has not been visited, it means we have found a new connected component. Increment `componentCount`.
  - Start a graph traversal (like Depth-First Search or Breadth-First Search) from node `i` to find and mark all nodes connected to it as visited.
- **Result**: After iterating through all nodes, `componentCount` will hold the total number of connected components.

## Optimized Space using Disjoint Set Union (DSU)
This approach improves upon the brute-force method by optimizing space. Instead of building and storing the entire graph in an adjacency list, we can use a Disjoint Set Union (DSU) data structure. As we find pairs of properties that should be connected, we `union` them in the DSU. This avoids the `O(n^2)` space complexity of an explicit graph representation.
**Time:** O(n^2 * m) - The nested loops run `O(n^2)` times. The `intersect` function takes `O(m)`. The DSU operations are nearly constant time, `O(α(n))`, so they don't change the overall complexity. · **Space:** O(n + m) - `O(n)` for the DSU's parent array and `O(m)` for the temporary `HashSet` used inside the loop for intersection calculation.
**Pros:** Excellent space complexity of `O(n + m)`.; Conceptually simple and avoids the overhead of building a full graph.; DSU is very fast for managing dynamic connectivity.
**Cons:** The time complexity remains `O(n^2 * m)`, which can be slow for large `n` and `m`.
### Explanation
The overall logic of iterating through all pairs of properties remains the same. However, the action taken when a connection is found is different. A DSU data structure is initialized with `n` sets, one for each property. When `intersect(properties[i], properties[j]) >= k`, we call `dsu.union(i, j)`. This operation merges the sets containing `i` and `j`. A well-implemented DSU with path compression and union by size/rank performs these operations in nearly constant time. The number of connected components is simply the number of disjoint sets remaining in the DSU at the end.

```java
import java.util.*;

class Solution {
    class DSU {
        int[] parent;
        int count;

        public DSU(int n) {
            parent = new int[n];
            count = n;
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }

        public int find(int i) {
            if (parent[i] == i) return i;
            return parent[i] = find(parent[i]); // Path compression
        }

        public void union(int i, int j) {
            int rootI = find(i);
            int rootJ = find(j);
            if (rootI != rootJ) {
                parent[rootI] = rootJ;
                count--;
            }
        }

        public int getCount() {
            return count;
        }
    }

    public int countConnectedComponents(int[][] properties, int k) {
        int n = properties.length;
        DSU dsu = new DSU(n);

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (intersect(properties[i], properties[j]) >= k) {
                    dsu.union(i, j);
                }
            }
        }

        return dsu.getCount();
    }

    private int intersect(int[] a, int[] b) {
        Set<Integer> setA = new HashSet<>();
        for (int val : a) {
            setA.add(val);
        }

        Set<Integer> common = new HashSet<>();
        for (int val : b) {
            if (setA.contains(val)) {
                common.add(val);
            }
        }
        return common.size();
    }
}
```
### Algorithm
- **Data Structure**: Use a Disjoint Set Union (DSU) data structure, also known as Union-Find. It is highly efficient for tracking connected components.
- **Initialization**: Create a DSU structure for `n` nodes. Initially, each node is its own parent, representing `n` separate components.
- **Edge Processing**: 
  - Iterate through every possible pair of properties `(properties[i], properties[j])` where `i < j`.
  - For each pair, calculate `intersect(properties[i], properties[j])` using a `HashSet` as in the previous approach.
  - If the intersection size is `>= k`, it means there's an edge between `i` and `j`. Instead of storing this edge, we immediately merge the components of `i` and `j` using the `union` operation in the DSU.
- **Result**: The DSU structure maintains a count of the disjoint sets. After checking all pairs, this count is the number of connected components in the graph.

## Time-Optimized Approach with Inverted Index
This approach aims to optimize the time complexity by avoiding a blind `O(n^2)` check of all pairs. It uses an inverted index to quickly find properties that share common values. By grouping properties by the values they contain, we can more efficiently count the intersections between pairs. This method is particularly effective when the properties are sparse and don't share many values.
**Time:** O(n*m + Σ |L_v|^2) where L_v is the list of properties for value v. This is because for each value, we iterate through all pairs of properties in its list. In the worst case, this is `O(n^2 * m)`, but its practical performance is often much better. · **Space:** O(n*m + n^2) - The inverted index can store up to `O(n*m)` items in total across all lists. The `intersectionCounts` array used in this implementation takes `O(n^2)` space. A map-based counter for pairs would have a similar worst-case space.
**Pros:** Can be significantly faster than brute-force on average, especially for sparse inputs.; Algorithmically more efficient as it avoids redundant work by pre-processing.
**Cons:** More complex to implement than the brute-force approaches.; The space complexity of `O(n*m)` can be larger than the simple DSU approach, though it's often manageable given the constraints.; The worst-case time complexity is not asymptotically better than brute-force.
### Explanation
First, we pre-process the input to build an inverted index. This map, `valueToProperties`, tells us exactly which properties contain any given value. This takes `O(n*m)` time.

Then, instead of comparing `properties[i]` and `properties[j]` directly, we can build the intersection counts more intelligently. For each property `i`, we can determine its intersection with all other properties `j` by looking at the values it contains. For each value `v` in `properties[i]`, we know it is also in every property listed in `valueToProperties.get(v)`. By aggregating these counts, we can find all pairs `(i, j)` whose intersection is at least `k` and union them using a DSU.

This avoids re-computing intersections from scratch for every pair and instead builds them up. While the worst-case time complexity remains `O(n^2 * m)`, the actual performance is proportional to the total number of shared values across all pairs, which can be significantly less.

```java
import java.util.*;

class Solution {
    class DSU {
        int[] parent;
        int count;
        public DSU(int n) {
            parent = new int[n];
            count = n;
            for (int i = 0; i < n; i++) parent[i] = i;
        }
        public int find(int i) {
            if (parent[i] == i) return i;
            return parent[i] = find(parent[i]);
        }
        public void union(int i, int j) {
            int rootI = find(i);
            int rootJ = find(j);
            if (rootI != rootJ) {
                parent[rootI] = rootJ;
                count--;
            }
        }
        public int getCount() { return count; }
    }

    public int countConnectedComponents(int[][] properties, int k) {
        int n = properties.length;
        if (n == 0) return 0;

        // 1. Build inverted index
        Map<Integer, List<Integer>> valueToProperties = new HashMap<>();
        for (int i = 0; i < n; i++) {
            Set<Integer> uniqueValues = new HashSet<>();
            for (int val : properties[i]) {
                uniqueValues.add(val);
            }
            for (int val : uniqueValues) {
                valueToProperties.computeIfAbsent(val, v -> new ArrayList<>()).add(i);
            }
        }

        DSU dsu = new DSU(n);

        // 2. Use index to find connections
        // We can iterate through the lists in the inverted index.
        // For each list, all pairs of nodes within it share at least one value.
        int[] intersectionCounts = new int[n * n]; // Flattened 2D array for pair counts

        for (List<Integer> propIndices : valueToProperties.values()) {
            for (int i = 0; i < propIndices.size(); i++) {
                for (int j = i + 1; j < propIndices.size(); j++) {
                    int u = propIndices.get(i);
                    int v = propIndices.get(j);
                    // Ensure a consistent order for the pair (u, v)
                    if (u > v) { int temp = u; u = v; v = temp; }
                    
                    int pairIndex = u * n + v;
                    intersectionCounts[pairIndex]++;
                    if (intersectionCounts[pairIndex] == k) {
                        dsu.union(u, v);
                    }
                }
            }
        }

        return dsu.getCount();
    }
}
```
### Algorithm
- **Inverted Index**: Create a map `valueToProperties` where keys are the integer values (1-100) and values are lists of property indices that contain that integer.
- **Build Index**: Iterate through each property `properties[i]`. For each unique value `v` in `properties[i]`, add the index `i` to the list `valueToProperties.get(v)`. This step takes `O(n*m)`.
- **Count Intersections and Union**: 
  - Initialize a DSU structure for `n` nodes.
  - Iterate through each property index `i` from `0` to `n-1`.
  - For each `i`, use a temporary map `pairCounts` to store intersection counts with other properties `j > i`.
  - For each unique value `v` in `properties[i]`, retrieve the list of properties `L_v = valueToProperties.get(v)`.
  - For each property index `j` in `L_v` (where `j > i`), increment its count in `pairCounts`.
  - After processing all values for property `i`, iterate through `pairCounts`. If `count >= k` for any `j`, perform `dsu.union(i, j)`.
- **Result**: The final count of components is retrieved from the DSU.

# Solutions
### Java

```java
class Solution {
private
  List<Integer>[] g;
private
  boolean[] vis;
public
  int numberOfComponents(int[][] properties, int k) {
    int n = properties.length;
    g = new List[n];
    Set<Integer>[] ss = new Set[n];
    Arrays.setAll(g, i->new ArrayList<>());
    Arrays.setAll(ss, i->new HashSet<>());
    for (int i = 0; i < n; ++i) {
      for (int x : properties[i]) {
        ss[i].add(x);
      }
    }
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < i; ++j) {
        int cnt = 0;
        for (int x : ss[i]) {
          if (ss[j].contains(x)) {
            ++cnt;
          }
        }
        if (cnt >= k) {
          g[i].add(j);
          g[j].add(i);
        }
      }
    }
    int ans = 0;
    vis = new boolean[n];
    for (int i = 0; i < n; ++i) {
      if (!vis[i]) {
        dfs(i);
        ++ans;
      }
    }
    return ans;
  }
private
  void dfs(int i) {
    vis[i] = true;
    for (int j : g[i]) {
      if (!vis[j]) {
        dfs(j);
      }
    }
  }
}

```

### CPP

```cpp
class Solution {
public:
  int numberOfComponents(vector<vector<int>> &properties, int k) {
    int n = properties.size();
    unordered_set<int> ss[n];
    vector<int> g[n];
    for (int i = 0; i < n; ++i) {
      for (int x : properties[i]) {
        ss[i].insert(x);
      }
    }
    for (int i = 0; i < n; ++i) {
      auto &s1 = ss[i];
      for (int j = 0; j < i; ++j) {
        auto &s2 = ss[j];
        int cnt = 0;
        for (int x : s1) {
          if (s2.contains(x)) {
            ++cnt;
          }
        }
        if (cnt >= k) {
          g[i].push_back(j);
          g[j].push_back(i);
        }
      }
    }
    int ans = 0;
    vector<bool> vis(n);
    auto dfs = [&](this auto &&dfs, int i) -> void {
      vis[i] = true;
      for (int j : g[i]) {
        if (!vis[j]) {
          dfs(j);
        }
      }
    };
    for (int i = 0; i < n; ++i) {
      if (!vis[i]) {
        dfs(i);
        ++ans;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def numberOfComponents(self, properties: List[List[int]], k: int) -> int: def dfs(i: int) -> None: vis[i] = True for j in g[i]: if not vis[j]: dfs(j) n = len(properties) ss = list(map(set, properties)) g = [[] for _ in range(n)] for i, s1 in enumerate(ss): for j in range(i): s2 = ss[j] if len(s1 & s2) >= k: g[i]. append(j) g[j]. append(i) ans = 0 vis = [False] * n for i in range(n): if not vis[i]: dfs(i) ans += 1 return ans

```