3493. Properties Graph

MediumDepth-First SearchBreadth-First SearchUnion FindGraphArrayHash Table

Problem Description

You are given a 2D integer array properties with 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 within the range [0, n - 1] and i != j.

Return the number of connected components in the resulting graph.

Intuition

To solve this problem, we first need to understand the concept of constructing a graph based on common elements in arrays. Each array in properties represents a node, and we draw an edge between two nodes if the number of elements they share is at least k.

Graph Construction: Transform each array in properties into a set. This will help efficiently compute the number of common elements between any two arrays by using set intersection.
Edge Creation: For each pair of arrays, compute the intersection of their sets. If the size of the intersection is at least k, establish an edge between the respective nodes in the graph.
Finding Connected Components: Utilize Depth-First Search (DFS) to determine the number of connected components. Initialize a visited list to keep track of which nodes have been explored. Traverse each node, and if it hasn't been visited, initiate a DFS from that node, marking all reachable nodes from it as visited and incrementing the connected components count.

By employing this approach, we can efficiently calculate how all nodes connect in a meaningful way according to the problem's requirements.

Learn more about Depth-First Search, Breadth-First Search, Union Find and Graph patterns.

Solution Approach

Solution 1: Hash Table + DFS

The solution utilizes a combination of hash tables and depth-first search (DFS) to determine the number of connected components in the graph created from the properties array.

Convert Arrays to Sets:
- First, convert each array in properties to a set and store these in an array called ss. This transformation allows efficient computation of intersections between sets, enabling us to swiftly determine the number of common elements.
```
ss = list(map(set, properties))
```

Graph Construction:

Create an adjacency list g to represent the graph, where g[i] contains all nodes that are adjacent to node i.
For each pair of sets (i, j) where j < i, check if the intersection of the sets has a size of at least k. If the condition holds, create edges between the nodes i and j in the adjacency list.

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)

Determine Connected Components Using DFS:

Initialize a visited list vis to track which nodes have been visited.
Iterate over all nodes, and whenever an unvisited node is found, perform a DFS starting from that node to visit all reachable nodes. After the DFS completes, increment the count of connected components.

vis = [False] * n

def dfs(i: int) -> None:
    vis[i] = True
    for j in g[i]:
        if not vis[j]:
            dfs(j)

ans = 0
for i in range(n):
    if not vis[i]:
        dfs(i)
        ans += 1

This approach ensures efficient graph traversal and connectivity checking, combining the power of data structures like sets for intersection operations and the DFS algorithm for component counting.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through an example to demonstrate the solution approach. Consider the following 2D integer array properties and the integer k:

properties = [
    [1, 2, 3],
    [2, 3, 4],
    [4, 5, 6],
    [5, 6, 7]
]
k = 2

The task is to find the number of connected components in the graph constructed from these properties.

Step 1: Convert Arrays to Sets

First, we convert each array in properties to a set:

ss = [
    {1, 2, 3},
    {2, 3, 4},
    {4, 5, 6},
    {5, 6, 7}
]

Step 2: Graph Construction

Next, we create an adjacency list g to represent the graph. For each pair of sets (i, j), where j < i, we check if the intersection size is at least k.

Compare {1, 2, 3} and {2, 3, 4}: Common elements are {2, 3} (size 2, meets the requirement). Add edge between nodes 0 and 1.
Compare {2, 3, 4} and {4, 5, 6}: Common element is {4} (size 1, does not meet the requirement). No edge added.
Compare {4, 5, 6} and {5, 6, 7}: Common elements are {5, 6} (size 2, meets the requirement). Add edge between nodes 2 and 3.

The adjacency list g becomes:

g = [
    [1],    # Node 0 is connected to Node 1
    [0],    # Node 1 is connected to Node 0
    [3],    # Node 2 is connected to Node 3
    [2]     # Node 3 is connected to Node 2
]

Step 3: Determine Connected Components Using DFS

Initialize a visited list vis:

vis = [False, False, False, False]

Perform DFS on each unvisited node:

Start with node 0, mark as visited, then visit node 1 through DFS. Both nodes 0 and 1 are marked as visited, forming one connected component.
Move to node 2, mark as visited, then visit node 3 through DFS. Both nodes 2 and 3 are marked as visited, forming another connected component.

The final count of connected components is:

ans = 2

Thus, the graph contains 2 connected components. This walkthrough demonstrates the solution approach using a combination of hash tables, sets for efficient intersection checking, and DFS for discovering connected components in the graph.

Solution Implementation

1from typing import List
2
3class Solution:
4    def numberOfComponents(self, properties: List[List[int]], k: int) -> int:
5        def dfs(node: int) -> None:
6            """Depth-First Search to explore and mark all nodes in the same component."""
7            visited[node] = True  # Mark current node as visited
8            for neighbor in graph[node]:
9                if not visited[neighbor]:  # Visit each unvisited neighbor
10                    dfs(neighbor)
11
12        # Number of properties
13        n = len(properties)
14        # Convert each sublist of properties to a set for easier intersection
15        sets = [set(prop) for prop in properties]
16        # Prepare the adjacency list for the graph
17        graph = [[] for _ in range(n)]
18        for i, set1 in enumerate(sets):
19            for j in range(i):
20                set2 = sets[j]
21                # Check if the intersection of two sets has at least 'k' elements
22                if len(set1 & set2) >= k:
23                    graph[i].append(j)  # Connect node i to node j
24                    graph[j].append(i)  # Connect node j to node i
25
26        # Initialize component counter and visited list
27        component_count = 0
28        visited = [False] * n
29        for i in range(n):
30            if not visited[i]:  # Start a new DFS if node `i` is not visited
31                dfs(i)
32                component_count += 1  # Increment the component count
33
34        return component_count
35

1import java.util.*;
2
3class Solution {
4    // Graph representation
5    private List<Integer>[] graph;
6    // Visited array for tracking visited nodes
7    private boolean[] visited;
8
9    // Method to calculate the number of connected components in the graph
10    public int numberOfComponents(int[][] properties, int k) {
11        int n = properties.length;
12        // Initialize the graph and set arrays
13        graph = new List[n];
14        Set<Integer>[] sets = new Set[n];
15        Arrays.setAll(graph, i -> new ArrayList<>());
16        Arrays.setAll(sets, i -> new HashSet<>());
17
18        // Populate the sets array with the properties
19        for (int i = 0; i < n; ++i) {
20            for (int value : properties[i]) {
21                sets[i].add(value);
22            }
23        }
24
25        // Build the graph with an edge between nodes if they share at least k elements
26        for (int i = 0; i < n; ++i) {
27            for (int j = 0; j < i; ++j) {
28                int sharedCount = 0;
29                // Count the common elements between the sets of two nodes
30                for (int value : sets[i]) {
31                    if (sets[j].contains(value)) {
32                        ++sharedCount;
33                    }
34                }
35                // Add an edge if the shared count is >= k
36                if (sharedCount >= k) {
37                    graph[i].add(j);
38                    graph[j].add(i);
39                }
40            }
41        }
42
43        // Number of connected components
44        int componentCount = 0;
45        visited = new boolean[n];
46        // Perform DFS to find all connected components
47        for (int i = 0; i < n; ++i) {
48            if (!visited[i]) {
49                dfs(i);
50                ++componentCount;
51            }
52        }
53
54        return componentCount;
55    }
56
57    // Depth-First Search to traverse any component completely
58    private void dfs(int node) {
59        visited[node] = true;
60        for (int neighbor : graph[node]) {
61            if (!visited[neighbor]) {
62                dfs(neighbor);
63            }
64        }
65    }
66}
67

1#include <vector>
2#include <unordered_set>
3#include <functional>
4
5class Solution {
6public:
7    int numberOfComponents(std::vector<std::vector<int>>& properties, int k) {
8        int n = properties.size();
9
10        // Array of unordered sets to store unique properties for each entity
11        std::unordered_set<int> propertySets[n];
12
13        // Graph adjacency list
14        std::vector<int> graph[n];
15
16        // Fill property sets for each item
17        for (int i = 0; i < n; ++i) {
18            for (int property : properties[i]) {
19                propertySets[i].insert(property);
20            }
21        }
22
23        // Build the graph based on the condition that there are at least `k` common properties
24        for (int i = 0; i < n; ++i) {
25            auto& currentSet = propertySets[i];
26            for (int j = 0; j < i; ++j) {
27                auto& compareSet = propertySets[j];
28                int commonCount = 0;
29
30                // Count common properties between i and j
31                for (int property : currentSet) {
32                    if (compareSet.contains(property)) {
33                        ++commonCount;
34                    }
35                }
36
37                // If common properties are at least k, create a bi-directional edge in the graph
38                if (commonCount >= k) {
39                    graph[i].push_back(j);
40                    graph[j].push_back(i);
41                }
42            }
43        }
44
45        int componentCount = 0;
46        std::vector<bool> visited(n, false);
47
48        // Lambda function to perform Depth-First Search (DFS)
49        std::function<void(int)> dfs = [&](int node) -> void {
50            visited[node] = true;
51            for (int neighbor : graph[node]) {
52                if (!visited[neighbor]) {
53                    dfs(neighbor);
54                }
55            }
56        };
57
58        // Loop through each node and start a DFS if it hasn't been visited
59        for (int i = 0; i < n; ++i) {
60            if (!visited[i]) {
61                dfs(i);
62                ++componentCount;  // Increment the component count for each DFS initiation
63            }
64        }
65
66        return componentCount;  // Return the total number of connected components
67    }
68};
69

1// Function to determine the number of connected components based on a threshold of common elements referred to as k.
2function numberOfComponents(properties: number[][], k: number): number {
3    const n = properties.length;
4
5    // Array of sets to store unique elements for each property entry
6    const ss: Set<number>[] = Array.from({ length: n }, () => new Set());
7  
8    // Graph representation using adjacency lists
9    const g: number[][] = Array.from({ length: n }, () => []);
10
11    // Populate the sets with elements from the properties array
12    for (let i = 0; i < n; i++) {
13        for (const x of properties[i]) {
14            ss[i].add(x);
15        }
16    }
17
18    // Build graph connections based on common elements count satisfying the threshold k
19    for (let i = 0; i < n; i++) {
20        for (let j = 0; j < i; j++) {
21            let countCommon = 0;
22
23            // Count common elements between properties[i] and properties[j]
24            for (const x of ss[i]) {
25                if (ss[j].has(x)) {
26                    countCommon++;
27                }
28            }
29
30            // If common elements count is greater than or equal to k, connect nodes i and j
31            if (countCommon >= k) {
32                g[i].push(j);
33                g[j].push(i);
34            }
35        }
36    }
37
38    let connectedComponents = 0;
39  
40    // Visited array to track processed nodes
41    const visited: boolean[] = Array(n).fill(false);
42
43    const dfs = (index: number) => {
44        visited[index] = true;
45
46        // Recursively visit all adjacent nodes
47        for (const adjacent of g[index]) {
48            if (!visited[adjacent]) {
49                dfs(adjacent);
50            }
51        }
52    };
53
54    // Iterate over all nodes to identify separate connected components
55    for (let i = 0; i < n; i++) {
56        if (!visited[i]) {
57            dfs(i);
58            connectedComponents++;
59        }
60    }
61
62    // Return the total count of connected components
63    return connectedComponents;
64}
65

Time and Space Complexity

The time complexity of the code is O(n^2 \times m). This is derived from the nested loop where for each element in properties (of size n), you compare it with all previous elements, leading to a factor of n^2. For each comparison, you need to check the intersection of sets which takes O(m) time, where m is the number of elements in an attribute array.

The space complexity of the code is O(n \times m). This is due to storing the list of sets ss, where each set contains elements of an attribute array, leading to a space usage of O(n \times m).

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What are the most two important steps in writing a depth first search function? (Select 2)

Determine state to pass down to recursive function call

Determine return value

Determine how many recursive calls will be made

Tracing the recursive calls