#3493

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Properties Graph

Find the number of connected components in an undirected graph formed by properties arrays, using array scanning and hash lookup techniques.

array hash table depth first search breadth first search union find

Problem Statement

You are given a 2D integer array properties of 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. The task is to find the number of connected components in the graph.

Examples

Example 1

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

Output: 3

The graph formed has 3 connected components:

Example 2

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

Output: 1

The graph formed has 1 connected component:

Example 3

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

Output: 2

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

Solution Approach

Graph Construction

First, create an undirected graph using the properties array. For every pair of nodes i and j, calculate the intersection of their corresponding arrays using the intersect function. Add an edge if the intersection size is greater than or equal to k.

Find Connected Components

Once the graph is constructed, use depth-first search (DFS) or breadth-first search (BFS) to traverse the graph. Count how many connected components exist, which corresponds to the number of DFS or BFS initiations needed to visit all nodes in the graph.

Optimize Array Intersection

To efficiently calculate the intersection of two arrays, use a hash set. The intersect(a, b) function can be implemented by converting arrays a and b into sets and returning the length of their intersection. This optimization reduces the computational complexity of checking array overlaps.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of this problem depends on the graph construction and the intersection calculation. Checking the intersection between two arrays has a complexity of O(m), where m is the length of the array. Constructing the graph requires O(n^2 * m) comparisons, where n is the number of properties. DFS or BFS to find connected components has a time complexity of O(n + e), where e is the number of edges.

What Interviewers Usually Probe

Ability to optimize array intersections using hash sets.
Familiarity with graph traversal techniques like DFS or BFS.
Understanding of connected components in graph theory.

Common Pitfalls or Variants

Common pitfalls

Not optimizing the intersection calculation, leading to excessive time complexity.
Missing edge cases where the intersection of two arrays is less than k.
Incorrect graph traversal or not accounting for all connected components.

Follow-up variants

Modify the problem to use weighted edges based on the number of intersecting integers.
Introduce additional constraints like limiting the number of edges or nodes.
Extend the problem to handle directed graphs instead of undirected.

FAQ

What is the main approach for solving the Properties Graph problem?

The main approach is constructing an undirected graph by checking array intersections, and then using DFS or BFS to find the number of connected components.

How can we optimize the array intersection step in this problem?

By using hash sets, the intersection operation can be optimized to reduce time complexity compared to a naive comparison approach.

What is the time complexity of the Properties Graph problem?

The time complexity is O(n^2 * m) for graph construction, with O(n + e) for the graph traversal where e is the number of edges.

What does `intersect(a, b)` return?

intersect(a, b) returns the number of distinct integers common between the two arrays a and b.

How does DFS or BFS help in this problem?

DFS or BFS is used to traverse the graph and find connected components, counting how many separate groups of nodes are fully connected.

terminal

Solution

Solution 1: Hash Table + DFS

We first convert each attribute array into a hash table and store them in a hash table array $\textit{ss}$. We define a graph $\textit{g}$, where $\textit{g}[i]$ stores the indices of attribute arrays that are connected to $\textit{properties}[i]$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

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

Continue Practicing

#3607 power grid maintenance #2368 reachable nodes with restrictions #928 minimize malware spread ii