Given a 2D array arr[] and value K, where each list in arr[] represents a point on Cartesian coordinates, the task is to group the given points if the distance between them is less than or equal to K and find the total number of disjoint groups.
Note: If points ‘a’ and ‘b’ are in the same group and ‘a’, ‘d’ are in the same group then ‘b’ and ‘d’ are also in the same group.
Examples:
Input: arr[] = {{73, -62}, {2, 2}, {3, 3}}, K = 1
Output: 3
Explanation: There are no two points which have distance = 1.
So all three points form different disjoint sets.Input: arr[] = {{3, 6}, {4, 2}, {3, 3}, {4, 9}}, K = 2
Output: 3
Explanation: The points{4, 2} and {3, 3} form a group.
An approach using Disjoint set union:
The idea to solve this problem is based on the concept of disjoint set union.
Assume all points as a disjoint group. So, number of disjoint groups initially will be N (N is the number of points in the given array). Generate all the possible pairs of points in the given array arr[], then check if the distance between them is less than or equals to K or not. If condition is satisfied, then merge them together and reduce the count of number of disjoint sets by 1.
Follow the steps below to implement the above idea:
- Create a parent and rank array of size N, where N is the number of points in the given array and a variable (say cc) to store the number of the connected components and initialize cc by N.
- Initialize the parent array for ith point to i (i.e parent[i] = i) and rank[i] = 1.
- Generate all the possible pairs of points in the given array arr
- Calculate the distance between the point and check if the distance between them is less than or equal to K or not
- if the distance is less the equal to k,
- Call the union1 function to merge these points.
- If merge is done successfully then reduce the count of cc by 1.
- if the distance is less the equal to k,
- Finally, return the count of cc.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to find the parent of a nodeint find(int x, vector<int>& parent){ if (x == parent[x]) return x; return parent[x] = find(parent[x], parent);}// Function to unite two setsbool union1(int x, int y, vector<int>& parent, vector<int>& rank){ int lx = find(x, parent); int ly = find(y, parent); // Condition of merging if (lx != ly) { if (rank[lx] > rank[ly]) { parent[ly] = lx; } else if (rank[lx] < rank[ly]) { parent[lx] = ly; } else { parent[lx] = ly; rank[ly] += 1; } // Return true for merging two // groups into one groups return true; } // Return false if points are // already merged. return false;}// Function to count the number of groups// formed after grouping the pointsint solve(vector<vector<int> >& points, int k){ int n = points.size(), // cc is for number of // connected component cc = n; vector<int> parent(n), rank(n); for (int i = 0; i < n; i++) { parent[i] = i; rank[i] = 1; } // Iterate over all pairs of point for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { double x1 = points[i][0], y1 = points[i][1]; double x2 = points[j][0], y2 = points[j][1]; // Calculate the distance // between the points double dist = (double)sqrt(pow(x2 - x1, 2) + pow(y2 - y1, 2)); // Check the given condition if (dist <= k) { // Merge this pair of points // into one group bool merge = union1(i, j, parent, rank); // If these points are getting // merged then reduce the cc by 1; if (merge) cc--; } } } return cc;}// Driver codeint main(){ vector<vector<int> > arr = { { 73, -62 }, { 2, 2 }, { 3, 3 } }; int K = 1; int result = solve(arr, K); // Function Call cout << result << endl; return 0;} |
Java
// Java code to implement the approachimport java.io.*;class GFG { // Function to find the parent of a node public static int find(int x, int parent[]) { if (x == parent[x]) return x; return parent[x] = find(parent[x], parent); } // Function to unite two sets public static boolean union1(int x, int y, int parent[], int rank[]) { int lx = find(x, parent); int ly = find(y, parent); // Condition of merging if (lx != ly) { if (rank[lx] > rank[ly]) { parent[ly] = lx; } else if (rank[lx] < rank[ly]) { parent[lx] = ly; } else { parent[lx] = ly; rank[ly] += 1; } // Return true for merging two // groups into one groups return true; } // Return false if points are // already merged. return false; } // Function to count the number of groups // formed after grouping the points public static int solve(int points[][], int k) { int n = points.length, // cc is for number of // connected component cc = n; int parent[] = new int[n]; int rank[] = new int[n]; for (int i = 0; i < n; i++) { parent[i] = i; rank[i] = 1; } // Iterate over all pairs of point for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { double x1 = points[i][0], y1 = points[i][1]; double x2 = points[j][0], y2 = points[j][1]; // Calculate the distance // between the points double dist = (double)Math.sqrt( Math.pow(x2 - x1, 2) + Math.pow(y2 - y1, 2)); // Check the given condition if (dist <= k) { // Merge this pair of points // into one group boolean merge = union1(i, j, parent, rank); // If these points are getting // merged then reduce the cc by 1; if (merge == true) cc--; } } } return cc; } // Driver Code public static void main(String[] args) { int arr[][] = { { 73, -62 }, { 2, 2 }, { 3, 3 } }; int K = 1; int result = solve(arr, K); // Function Call System.out.println(result); }}// This code is contributed by Rohit Pradhan |
Python3
import mathclass GFG : # Function to find the parent of a node @staticmethod def find( x, parent) : if (x == parent[x]) : return x return parent[x] = GFG.find(parent[x], parent) # Function to unite two sets @staticmethod def union1( x, y, parent, rank) : lx = GFG.find(x, parent) ly = GFG.find(y, parent) # Condition of merging if (lx != ly) : if (rank[lx] > rank[ly]) : parent[ly] = lx elif(rank[lx] < rank[ly]) : parent[lx] = ly else : parent[lx] = ly rank[ly] += 1 # Return true for merging two # groups into one groups return True # Return false if points are # already merged. return False # Function to count the number of groups # formed after grouping the points @staticmethod def solve( points, k) : n = len(points) cc = n parent = [0] * (n) rank = [0] * (n) i = 0 while (i < n) : parent[i] = i rank[i] = 1 i += 1 # Iterate over all pairs of point i = 0 while (i < n) : j = i + 1 while (j < n) : x1 = points[i][0] y1 = points[i][1] x2 = points[j][0] y2 = points[j][1] # Calculate the distance # between the points dist = float(math.sqrt(math.pow(x2 - x1,2) + math.pow(y2 - y1,2))) # Check the given condition if (dist <= k) : # Merge this pair of points # into one group merge = GFG.union1(i, j, parent, rank) # If these points are getting # merged then reduce the cc by 1; if (merge == True) : cc -= 1 j += 1 i += 1 return cc # Driver Code @staticmethod def main( args) : arr = [[73, -62], [2, 2], [3, 3]] K = 1 result = GFG.solve(arr, K) # Function Call print(result) if __name__=="__main__": GFG.main([]) # This code is contributed by aadityaburujwale. |
C#
// C# code to implement the approachusing System;class GFG { // Function to find the parent of a node static int find(int x, int[] parent) { if (x == parent[x]) return x; return parent[x] = find(parent[x], parent); } // Function to unite two sets static bool union1(int x, int y, int[] parent, int[] rank) { int lx = find(x, parent); int ly = find(y, parent); // Condition of merging if (lx != ly) { if (rank[lx] > rank[ly]) { parent[ly] = lx; } else if (rank[lx] < rank[ly]) { parent[lx] = ly; } else { parent[lx] = ly; rank[ly] += 1; } // Return true for merging two // groups into one groups return true; } // Return false if points are // already merged. return false; } // Function to count the number of groups // formed after grouping the points static int solve(int[, ] points, int k, int n, int m) { // cc is for number of // connected component int cc = n; int[] parent = new int[n]; int[] rank = new int[n]; for (int i = 0; i < n; i++) { parent[i] = i; rank[i] = 1; } // Iterate over all pairs of point for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { double x1 = (double)points[i, 0], y1 = (double)points[i, 1]; double x2 = (double)points[j, 0], y2 = (double)points[j, 1]; // Calculate the distance // between the points double dist = (double)Math.Sqrt( Math.Pow(x2 - x1, 2) + Math.Pow(y2 - y1, 2)); // Check the given condition if (dist <= k) { // Merge this pair of points // into one group bool merge = union1(i, j, parent, rank); // If these points are getting // merged then reduce the cc by 1; if (merge) cc--; } } } return cc; } // Driver code public static void Main(string[] args) { int[, ] arr = new int[3, 2] { { 73, -62 }, { 2, 2 }, { 3, 3 } }; int N = 3; int M = 2; int K = 1; int result = solve(arr, K, N, M); // Function Call Console.Write(result); }}// This code is contributed by garg28harsh. |
Javascript
<script> // JavaScript code to implement the approach // Function to find the parent of a node const find = (x, parent) => { if (x == parent[x]) return x; return parent[x] = find(parent[x], parent); } // Function to unite two sets const union1 = (x, y, parent, rank) => { let lx = find(x, parent); let ly = find(y, parent); // Condition of merging if (lx != ly) { if (rank[lx] > rank[ly]) { parent[ly] = lx; } else if (rank[lx] < rank[ly]) { parent[lx] = ly; } else { parent[lx] = ly; rank[ly] += 1; } // Return true for merging two // groups into one groups return true; } // Return false if points are // already merged. return false; } // Function to count the number of groups // formed after grouping the points const solve = (points, k) => { let n = points.length, // cc is for number of // connected component cc = n; let parent = new Array(n).fill(0), rank = new Array(n).fill(0); for (let i = 0; i < n; i++) { parent[i] = i; rank[i] = 1; } // Iterate over all pairs of point for (let i = 0; i < n; i++) { for (let j = i + 1; j < n; j++) { let x1 = points[i][0], y1 = points[i][1]; let x2 = points[j][0], y2 = points[j][1]; // Calculate the distance // between the points let dist = Math.sqrt(Math.pow(x2 - x1, 2) + Math.pow(y2 - y1, 2)); // Check the given condition if (dist <= k) { // Merge this pair of points // into one group let merge = union1(i, j, parent, rank); // If these points are getting // merged then reduce the cc by 1; if (merge) cc--; } } } return cc; } // Driver code let arr = [[73, -62], [2, 2], [3, 3]]; let K = 1; let result = solve(arr, K); // Function Call document.write(result); // This code is contributed by rakeshsahni</script> |
Output
3
Time Complexity: O(N2), where N is the number of points in the given array.
Auxiliary Space: O(N), for storing the parents and rank array in UnionFind.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
