We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Properties Graph

Number: 3809

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given a 2D array of integers called properties where each properties[i] represents the properties of a node, and an integer k, build an undirected graph by connecting two nodes i and j (i ≠ j) if the number of distinct integers common to both properties[i] and properties[j] is greater than or equal to k. The goal is to determine the number of connected components in the resulting graph.

Key Insights

  • Convert each properties[i] array into a set to quickly find distinct common integers.
  • Use a helper function to count the number of common elements between two sets.
  • An edge exists between two nodes if the count of common distinct integers is at least k.
  • Explore the graph using either DFS/BFS or use the Union Find (Disjoint Set Union) data structure to merge connected nodes.
  • Since n is at most 100, iterating pairwise over nodes is computationally acceptable.

Space and Time Complexity

Time Complexity: O(n^2 * m) in the worst case, where n is the number of nodes and m is the maximum length of each properties list (after converting to a set, the average intersection operation is proportional to the smaller set size).
Space Complexity: O(n * m) for storing the sets and O(n) for the Union Find or DFS visited array.

Solution

The solution first converts each properties list into a set for quick look-up and duplicate removal. Then, for every pair of nodes (i, j), it checks if the intersection size of their property sets is at least k. If it is, they are connected by an edge.

The problem can be solved in two ways:

  1. Depth-First Search (DFS)/Breadth-First Search (BFS): Build an adjacency list and use DFS/BFS to traverse nodes, counting each connected component.
  2. Union Find (Disjoint Set Union): Iterate over all pairs of nodes and union their sets if they satisfy the connection criteria. Finally, count distinct parents to get the number of connected components.

Both approaches leverage the idea of iterating over all pairs and using set intersection to check the connection condition.

Code Solutions

# Python solution using Union Find
# Function to perform union-find operations
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if px != py:
            self.parent[py] = px

def countComponents(properties, k):
    n = len(properties)
    # Convert each properties list to a set
    propertySets = [set(prop) for prop in properties]
    
    uf = UnionFind(n)
    
    # Iterate over all pairs to check if they have at least k common properties.
    for i in range(n):
        for j in range(i + 1, n):
            # Count intersection size
            # Use set intersection to count distinct common integers
            if len(propertySets[i] & propertySets[j]) >= k:
                uf.union(i, j)
    
    # Count number of distinct roots = connected components
    components = set()
    for i in range(n):
        components.add(uf.find(i))
    return len(components)

# Example usage:
properties = [[1,2],[1,1],[3,4],[4,5],[5,6],[7,7]]
k = 1
print(countComponents(properties, k))  # Expected output: 3
← Back to All Questions