3493. Properties Graph
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.
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 <= 1001 <= m == properties[i].length <= 1001 <= properties[i][j] <= 1001 <= k <= m
Solutions
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]$.
Then, we iterate through all attribute hash tables. For each pair of attribute hash tables $(i, j)$ where $j < i$, we check whether the number of common elements between them is at least $k$. If so, we add an edge from $i$ to $j$ in the graph $\textit{g}$, as well as an edge from $j$ to $i$.
Finally, we use Depth-First Search (DFS) to compute the number of connected components in the graph $\textit{g}$.
The time complexity is $O(n^2 \times m)$, and the space complexity is $O(n \times m)$, where $n$ is the length of the attribute arrays and $m$ is the number of elements in an attribute array.
Python3
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
Java
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);
}
}
}
}
C++
class Solution {
public:
int numberOfComponents(vector<vector<int>>& properties, int k) {
int n = properties.size();
unordered_set<int> ss[n];
vector<int> g[n];
for (int i = 0; i < n; ++i) {
for (int x : properties[i]) {
ss[i].insert(x);
}
}
for (int i = 0; i < n; ++i) {
auto& s1 = ss[i];
for (int j = 0; j < i; ++j) {
auto& s2 = ss[j];
int cnt = 0;
for (int x : s1) {
if (s2.contains(x)) {
++cnt;
}
}
if (cnt >= k) {
g[i].push_back(j);
g[j].push_back(i);
}
}
}
int ans = 0;
vector<bool> vis(n);
auto dfs = [&](this auto&& dfs, int i) -> void {
vis[i] = true;
for (int j : g[i]) {
if (!vis[j]) {
dfs(j);
}
}
};
for (int i = 0; i < n; ++i) {
if (!vis[i]) {
dfs(i);
++ans;
}
}
return ans;
}
};
Go
func numberOfComponents(properties [][]int, k int) (ans int) {
n := len(properties)
ss := make([]map[int]struct{}, n)
g := make([][]int, n)
for i := 0; i < n; i++ {
ss[i] = make(map[int]struct{})
for _, x := range properties[i] {
ss[i][x] = struct{}{}
}
}
for i := 0; i < n; i++ {
for j := 0; j < i; j++ {
cnt := 0
for x := range ss[i] {
if _, ok := ss[j][x]; ok {
cnt++
}
}
if cnt >= k {
g[i] = append(g[i], j)
g[j] = append(g[j], i)
}
}
}
vis := make([]bool, n)
var dfs func(int)
dfs = func(i int) {
vis[i] = true
for _, j := range g[i] {
if !vis[j] {
dfs(j)
}
}
}
for i := 0; i < n; i++ {
if !vis[i] {
dfs(i)
ans++
}
}
return
}
TypeScript
function numberOfComponents(properties: number[][], k: number): number {
const n = properties.length;
const ss: Set<number>[] = Array.from({ length: n }, () => new Set());
const g: number[][] = Array.from({ length: n }, () => []);
for (let i = 0; i < n; i++) {
for (const x of properties[i]) {
ss[i].add(x);
}
}
for (let i = 0; i < n; i++) {
for (let j = 0; j < i; j++) {
let cnt = 0;
for (const x of ss[i]) {
if (ss[j].has(x)) {
cnt++;
}
}
if (cnt >= k) {
g[i].push(j);
g[j].push(i);
}
}
}
let ans = 0;
const vis: boolean[] = Array(n).fill(false);
const dfs = (i: number) => {
vis[i] = true;
for (const j of g[i]) {
if (!vis[j]) {
dfs(j);
}
}
};
for (let i = 0; i < n; i++) {
if (!vis[i]) {
dfs(i);
ans++;
}
}
return ans;
}