Properties Graph
MedPrompt
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:
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:
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 <= 1001 <= m == properties[i].length <= 1001 <= properties[i][j] <= 1001 <= k <= m
Approaches
3 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Graph Representation: Use an adjacency list,
List<Integer>[] adj, to represent the graph, whereadj[i]stores all neighbors of nodei. - Graph Construction:
- Iterate through every possible pair of properties
(properties[i], properties[j])wherei < j. - For each pair, calculate the number of common distinct elements. A simple way is to convert
properties[i]into aHashSetfor O(1) average time lookups. - Then, iterate through the unique elements of
properties[j]and count how many are present in the set ofproperties[i]. - If the count of common elements is greater than or equal to
k, add an undirected edge between nodesiandjin the adjacency list.
- Iterate through every possible pair of properties
- Count Components:
- Initialize a
visitedboolean array of sizento keep track of visited nodes. - Initialize a counter for connected components,
componentCount, to zero. - Iterate through each node from
0ton-1. - If a node
ihas not been visited, it means we have found a new connected component. IncrementcomponentCount. - Start a graph traversal (like Depth-First Search or Breadth-First Search) from node
ito find and mark all nodes connected to it as visited.
- Initialize a
- Result: After iterating through all nodes,
componentCountwill hold the total number of connected components.
Walkthrough
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.
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); } } }}Complexity
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.
Trade-offs
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 largern.Building the full adjacency list can be memory-intensive if the graph is dense.
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.
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
nnodes. Initially, each node is its own parent, representingnseparate components. - Edge Processing:
- Iterate through every possible pair of properties
(properties[i], properties[j])wherei < j. - For each pair, calculate
intersect(properties[i], properties[j])using aHashSetas in the previous approach. - If the intersection size is
>= k, it means there's an edge betweeniandj. Instead of storing this edge, we immediately merge the components ofiandjusing theunionoperation in the DSU.
- Iterate through every possible pair of properties
- 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.
Walkthrough
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.
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(); }}Complexity
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.
Trade-offs
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 largenandm.
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.
Algorithm
- Inverted Index: Create a map
valueToPropertieswhere 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 valuevinproperties[i], add the indexito the listvalueToProperties.get(v). This step takesO(n*m). - Count Intersections and Union:
- Initialize a DSU structure for
nnodes. - Iterate through each property index
ifrom0ton-1. - For each
i, use a temporary mappairCountsto store intersection counts with other propertiesj > i. - For each unique value
vinproperties[i], retrieve the list of propertiesL_v = valueToProperties.get(v). - For each property index
jinL_v(wherej > i), increment its count inpairCounts. - After processing all values for property
i, iterate throughpairCounts. Ifcount >= kfor anyj, performdsu.union(i, j).
- Initialize a DSU structure for
- Result: The final count of components is retrieved from the DSU.
Walkthrough
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.
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(); }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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); } } }}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; }};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 ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.