3493. Properties Graph LeetCode Solution
In this guide, you will get 3493. Properties Graph LeetCode Solution with the best time and space complexity. The solution to Properties Graph problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Table of Contents
- Problem Statement
- Complexity Analysis
- Properties Graph solution in C++
- Properties Graph solution in Java
- Properties Graph solution in Python
- Additional Resources
Problem Statement of Properties Graph
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
Complexity Analysis
- Time Complexity: O(n^2\log^* n)
- Space Complexity: O(n)
3493. Properties Graph LeetCode Solution in C++
class UnionFind {
public:
UnionFind(int n) : count(n), id(n), rank(n) {
iota(id.begin(), id.end(), 0);
}
void unionByRank(int u, int v) {
const int i = find(u);
const int j = find(v);
if (i == j)
return;
if (rank[i] < rank[j]) {
id[i] = j;
} else if (rank[i] > rank[j]) {
id[j] = i;
} else {
id[i] = j;
++rank[j];
}
--count;
}
int getCount() const {
return count;
}
private:
int count;
vector<int> id;
vector<int> rank;
int find(int u) {
return id[u] == u ? u : id[u] = find(id[u]);
}
};
class Solution {
public:
int numberOfComponents(vector<vector<int>>& properties, int k) {
const int n = properties.size();
const vector<set<int>> propertySets = getPropertySets(properties);
UnionFind uf(n);
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j) {
vector<int> intersection;
std::set_intersection(propertySets[i].begin(), propertySets[i].end(),
propertySets[j].begin(), propertySets[j].end(),
std::back_inserter(intersection));
if (intersection.size() >= k)
uf.unionByRank(i, j);
}
return uf.getCount();
}
private:
vector<set<int>> getPropertySets(const vector<vector<int>>& properties) {
vector<set<int>> propertySets;
for (const vector<int>& property : properties)
propertySets.push_back({property.begin(), property.end()});
return propertySets;
}
};
/* code provided by PROGIEZ */3493. Properties Graph LeetCode Solution in Java
class UnionFind {
public UnionFind(int n) {
count = n;
id = new int[n];
rank = new int[n];
for (int i = 0; i < n; ++i)
id[i] = i;
}
public void unionByRank(int u, int v) {
final int i = find(u);
final int j = find(v);
if (i == j)
return;
if (rank[i] < rank[j]) {
id[i] = j;
} else if (rank[i] > rank[j]) {
id[j] = i;
} else {
id[i] = j;
++rank[j];
}
--count;
}
public int getCount() {
return count;
}
private int count;
private int[] id;
private int[] rank;
private int find(int u) {
return id[u] == u ? u : (id[u] = find(id[u]));
}
}
class Solution {
public int numberOfComponents(int[][] properties, int k) {
final int n = properties.length;
Set<Integer>[] propertySets = getPropertySets(properties);
UnionFind uf = new UnionFind(n);
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j) {
Set<Integer> intersection = new HashSet<>(propertySets[i]);
intersection.retainAll(propertySets[j]);
if (intersection.size() >= k)
uf.unionByRank(i, j);
}
return uf.getCount();
}
private Set<Integer>[] getPropertySets(int[][] properties) {
Set<Integer>[] propertySets = new Set[properties.length];
for (int i = 0; i < properties.length; ++i)
propertySets[i] = Arrays.stream(properties[i]).boxed().collect(Collectors.toSet());
return propertySets;
}
}
// code provided by PROGIEZ3493. Properties Graph LeetCode Solution in Python
class UnionFind:
def __init__(self, n: int):
self.count = n
self.id = list(range(n))
self.rank = [0] * n
def unionByRank(self, u: int, v: int) -> None:
i = self._find(u)
j = self._find(v)
if i == j:
return
if self.rank[i] < self.rank[j]:
self.id[i] = j
elif self.rank[i] > self.rank[j]:
self.id[j] = i
else:
self.id[i] = j
self.rank[j] += 1
self.count -= 1
def getCount(self) -> int:
return self.count
def _find(self, u: int) -> int:
if self.id[u] != u:
self.id[u] = self._find(self.id[u])
return self.id[u]
class Solution:
def numberOfComponents(self, properties: list[list[int]], k: int) -> int:
n = len(properties)
uf = UnionFind(n)
propertySets = [set(property) for property in properties]
for i, j in itertools.combinations(range(n), 2):
if len(propertySets[i] & propertySets[j]) >= k:
uf.unionByRank(i, j)
return uf.getCount()
# code by PROGIEZAdditional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.