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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Properties Graph

Difficulty: Medium

Problem Description

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.

Key Insights

  • The graph is constructed based on the number of common integers between the properties of each pair of nodes.
  • We need to count the number of connected components, which can be achieved using graph traversal techniques (DFS/BFS).
  • Efficiently calculating the intersection of two arrays can be done using sets, which allow for O(1) average time complexity for lookups.
  • The problem can be visualized as finding how many distinct clusters of nodes exist based on the defined edges.

Space and Time Complexity

Time Complexity: O(n^2 * m) - for each pair of nodes, we compute the intersection of their properties. Space Complexity: O(n * m) - for storing the properties and additional space for graph representation.

Solution

To solve the problem, we will use the following algorithm:

  1. Create a function intersect(a, b) that calculates the number of distinct common integers between two arrays using sets.
  2. Construct an adjacency list to represent the undirected graph based on the intersections.
  3. Utilize Depth-First Search (DFS) or Breadth-First Search (BFS) to traverse the graph and count the number of connected components.

Code Solutions

def intersect(a, b):
    return len(set(a) & set(b))

def count_connected_components(properties, k):
    n = len(properties)
    graph = [[] for _ in range(n)]
    
    # Build the graph
    for i in range(n):
        for j in range(i + 1, n):
            if intersect(properties[i], properties[j]) >= k:
                graph[i].append(j)
                graph[j].append(i)
    
    visited = [False] * n
    components_count = 0

    def dfs(node):
        stack = [node]
        while stack:
            current = stack.pop()
            for neighbor in graph[current]:
                if not visited[neighbor]:
                    visited[neighbor] = True
                    stack.append(neighbor)

    # Count connected components
    for i in range(n):
        if not visited[i]:
            visited[i] = True
            components_count += 1
            dfs(i)

    return components_count
← Back to All Questions