https://binarysearch.com/problems/Group-Points
Description
You are given a two-dimensional list of integers points
and an integer k
. Each list in points
is of the form (x, y)
representing Cartesian coordinates. Assuming you can group any point a
and b
if the Euclidean distance between them is ≤ k
, return the total number of disjoint groups.
Note that if points a
and b
are grouped and b
and c
are grouped, then a
and c
are in the same group.
Constraints:
-
n ≤ 1,000
wheren
is length ofpoints
.
Example 1
Input
points = [
[1, 1],
[2, 2],
[3, 3],
[10, 10],
[11, 11]
]
k = 2
Output
2
Explanation
There are two groups:
[1,1],[2,2],[3,3]
[10,10],[11,11]
Intuition
Union Find
Implementation
int p[10003];
int find(int x) {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
}
double distance(vector<int> a, vector<int> b) {
return sqrt(pow(a[0] - b[0], 2) + pow(a[1] - b[1], 2));
}
int solve(vector<vector<int>>& points, int k) {
int n = points.size();
for (int i = 0; i < n; i++) {
p[i] = i;
}
int groups = n;
for (int i = 0; i < n; i++) {
vector<int> a = points[i];
for (int j = i + 1; j < n; j++) {
vector<int> b = points[j];
if (distance(a, b) <= k && find(i) != find(j)) {
p[find(i)] = find(j);
groups--;
}
}
}
return groups;
}
Time Complexity
- Time: O(n^2)
- Space: O(n)
Top comments (0)