Group Points

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 where n is length of points.

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)