LeetCode 3493 - Properties Graph

The problem asks us to model a 2D array of integers, called properties, as an undirected graph. Each row of the array corresponds to a node in the graph. Two nodes are connected if the number of distinct integers they share is at least k.

leetcodemediumarrayhash-tabledepth-first-searchbreadth-first-searchunion-findgraph-theory

LeetCode Problem 3493

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Depth-First Search, Breadth-First Search, Union-Find, Graph Theory

Solution

Problem Understanding

The problem asks us to model a 2D array of integers, called properties, as an undirected graph. Each row of the array corresponds to a node in the graph. Two nodes are connected if the number of distinct integers they share is at least k. Our goal is to count the number of connected components in this graph.

In other words, we are given n lists of integers, each of length m, and an integer k. For every pair of lists, we need to determine how many integers they have in common. If the number of common integers is k or more, we draw an edge between the corresponding nodes. Once the graph is built, we need to determine how many isolated clusters of nodes exist.

Constraints give us some important observations: n and m are both up to 100, and the integers in the arrays are in the range [1, 100]. This means the graph can have at most 100 nodes, and comparisons between rows are feasible even with an O(n² * m) approach if done carefully. However, we should aim to optimize wherever possible. Edge cases include rows with repeated values, all rows being identical, or k being larger than the number of unique elements in any row.

Approaches

The brute-force approach involves comparing each pair of rows directly and counting the number of distinct integers in common. If the count meets or exceeds k, we add an edge in the adjacency list. After building the graph, we perform a standard DFS or BFS to count connected components. This approach works correctly but can be inefficient because checking intersections between all pairs is O(n² * m) and storing the adjacency list adds additional overhead.

The optimal approach leverages sets and Union-Find (Disjoint Set Union, DSU) to avoid explicitly constructing a full graph. By converting each row into a set of integers, we can compute intersections quickly using set operations. Union-Find allows us to dynamically merge nodes into connected components without traversing the adjacency list repeatedly. This reduces the overhead of repeatedly visiting nodes in BFS/DFS and is efficient for up to 100 nodes.

Approach Time Complexity Space Complexity Notes
Brute Force O(n² * m) O(n²) Directly compares each pair of rows, constructs adjacency list, then runs DFS/BFS
Optimal O(n² * m) O(n * m) Uses sets to compute intersections and Union-Find to merge components efficiently

Algorithm Walkthrough

  1. Convert each row in properties into a set to remove duplicates and allow fast intersection operations.
  2. Initialize a Union-Find data structure for n nodes. Each node initially belongs to its own component.
  3. Iterate over all unique pairs of nodes (i, j) where i < j.
  4. For each pair, compute the intersection of their sets.
  5. If the size of the intersection is at least k, union the two nodes in the Union-Find structure.
  6. After processing all pairs, count the number of unique components in Union-Find by counting distinct roots.

Why it works: The Union-Find structure ensures that whenever two nodes should be connected, their root is merged. After processing all edges, nodes in the same connected component share the same root, so counting distinct roots gives the exact number of connected components.

Python Solution

from typing import List

class UnionFind:
    def __init__(self, size: int):
        self.parent = list(range(size))
        self.rank = [0] * size
    
    def find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x: int, y: int) -> None:
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX == rootY:
            return
        if self.rank[rootX] > self.rank[rootY]:
            self.parent[rootY] = rootX
        elif self.rank[rootX] < self.rank[rootY]:
            self.parent[rootX] = rootY
        else:
            self.parent[rootY] = rootX
            self.rank[rootX] += 1

class Solution:
    def numberOfComponents(self, properties: List[List[int]], k: int) -> int:
        n = len(properties)
        uf = UnionFind(n)
        sets = [set(row) for row in properties]
        
        for i in range(n):
            for j in range(i + 1, n):
                if len(sets[i] & sets[j]) >= k:
                    uf.union(i, j)
        
        roots = {uf.find(i) for i in range(n)}
        return len(roots)

The Python solution first converts each row to a set to remove duplicates and enable fast intersection operations. The nested loops iterate over all pairs of nodes, performing intersection checks and merging nodes in Union-Find if they meet the threshold. Finally, the number of distinct roots in Union-Find corresponds to the number of connected components.

Go Solution

package main

func numberOfComponents(properties [][]int, k int) int {
    n := len(properties)
    
    parent := make([]int, n)
    rank := make([]int, n)
    for i := 0; i < n; i++ {
        parent[i] = i
        rank[i] = 0
    }
    
    find := func(x int) int {
        if parent[x] != x {
            parent[x] = find(parent[x])
        }
        return parent[x]
    }
    
    union := func(x, y int) {
        rootX := find(x)
        rootY := find(y)
        if rootX == rootY {
            return
        }
        if rank[rootX] > rank[rootY] {
            parent[rootY] = rootX
        } else if rank[rootX] < rank[rootY] {
            parent[rootX] = rootY
        } else {
            parent[rootY] = rootX
            rank[rootX]++
        }
    }
    
    sets := make([]map[int]struct{}, n)
    for i := 0; i < n; i++ {
        sets[i] = make(map[int]struct{})
        for _, val := range properties[i] {
            sets[i][val] = struct{}{}
        }
    }
    
    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            count := 0
            for val := range sets[i] {
                if _, ok := sets[j][val]; ok {
                    count++
                }
            }
            if count >= k {
                union(i, j)
            }
        }
    }
    
    roots := make(map[int]struct{})
    for i := 0; i < n; i++ {
        roots[find(i)] = struct{}{}
    }
    return len(roots)
}

The Go solution follows the same logic as Python. Go-specific considerations include using struct{} for set values to save memory and explicitly handling slices for Union-Find. The union and find functions are implemented as closures to avoid creating a separate struct type.

Worked Examples

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

i j sets[i] & sets[j] intersection size union?
0 1 {1} 1 Yes
0 2 {} 0 No
2 3 {4} 1 Yes
3 4 {5} 1 Yes
5 others {} 0 No

Connected components after union-find: {0,1}, {2,3,4}, {5} → total 3.

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

i j sets[i] & sets[j] size union?
0 1 {2,3} 2 Yes
1 2 {3,4} 2 Yes
0 2 {3} 1 No

All nodes merge into a single component → output 1.

Example 3: properties = [[1,1],[1,1]], k = 2

i j sets[i] & sets[j] size union?
0 1 {1} 1 No

No unions occur → two separate components → output 2.

Complexity Analysis

Measure Complexity Explanation
Time O(n² * m) We iterate over all pairs of rows and compute set intersections which take O(m) per pair
Space O(n * m) Storing sets for each row and Union-Find arrays

The n² factor comes from comparing all pairs, while m comes from computing intersections. Union-Find operations are effectively constant time due to path compression and rank optimization.

Test Cases

# Provided examples
assert Solution().numberOfComponents([[1,2],[1,1],[

We are given the algorithm naturally returns1whenn = 1`.