Scale Engineer

Properties Graph

Med
#3106Time: 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.
Algorithms
Depth-First SearchBreadth-First SearchUnion Find
Data structures
ArrayHash TableGraph

Prompt

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 <= 100
  • 1 <= m == properties[i].length <= 100
  • 1 <= properties[i][j] <= 100
  • 1 <= 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, where adj[i] stores all neighbors of node i.
  • Graph Construction:
    • Iterate through every possible pair of properties (properties[i], properties[j]) where i < j.
    • For each pair, calculate the number of common distinct elements. A simple way is to convert properties[i] into a HashSet for O(1) average time lookups.
    • Then, iterate through the unique elements of properties[j] and count how many are present in the set of properties[i].
    • If the count of common elements is greater than or equal to k, add an undirected edge between nodes i and j in the adjacency list.
  • Count Components:
    • Initialize a visited boolean array of size n to keep track of visited nodes.
    • Initialize a counter for connected components, componentCount, to zero.
    • Iterate through each node from 0 to n-1.
    • If a node i has not been visited, it means we have found a new connected component. Increment componentCount.
    • Start a graph traversal (like Depth-First Search or Breadth-First Search) from node i to find and mark all nodes connected to it as visited.
  • Result: After iterating through all nodes, componentCount will 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 larger n.

  • Building the full adjacency list can be memory-intensive if the graph is dense.

Solutions

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);      }    }  }}

Video 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.

← Previous

Previous problem

Next →

Next problem