Group Points

Hard
0/120
5 upvotes
Asked in company
Google inc

Problem statement

You are given an array ‘POINTS’ having ‘N’ points located in a 2D plane and an integer ‘K’. Your task is to group them in such a way that if the euclidean distance between two points is less than or equal to ‘K’, group them together. This relation is chainable.

For example, [P1,P2,P3], P1 to P2 <= ‘K’, P2 to P3<=k, P1 to P3>’K’. They are still in the same group. Return the number of groups formed.

For Example 
If the given POINTS array is [(0,0),(1,1),(3,3)] and ‘K’ = 2, then the number of groups will be 2.
One group will be [(0,0) , (1,1)] and other will be [(3,3)].
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of the input contains an integer, 'T,’ denoting the number of test cases.

The first line of each test case contains two integers, 'N’ denoting the number of points in the ‘POINTS’ array and ‘K’.

The next ‘N’ lines of each test case has two integers corresponding to the x and y coordinate of POINTS[i].
Output Format: 
For each test case, print a single integer corresponding to the number of groups.

Output for each test case will be printed in a separate line.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= N <= 3000
1 <= K <= 50.
-1000 <= X coordinate of 'POINTS'[i]  <= 1000
-1000 <= Y coordinate of ’POINTS’[i] <=1000

Time limit: 1 sec
Sample Input 1:
2
3 2
0 0
1 1
3 3
3 1
0 0
1 1
2 2
Sample Output 1:
2
3
Explanation of sample input 1:
For the first test case,
The distance between the first two points is √2, which is less than ‘K’. So they are grouped together. The distance between the third point and the second point is 2√2, which is greater than ‘K’.So it can’t be grouped together.So the groups are [(0,0) , (1,1)] , [(3,3)].The number of groups is 2. Hence the answer is 2.

For the second test case,
The distance between any pair of points is greater than ‘K’.So no points can be grouped together.So the groups are [(0,0)] , [(1,1)] , [(2,2)]. The number of groups is 3. Hence the answer is 3.
Sample Input 2:
2
4 2
-1 -2
0 -1
0 2
1 -1
3 2
1 -2 
2 -1 
2 1
Sample Output 2:
2
1
Hint

Try to iterate over each pair of points.

Approaches (2)
Brute Force using Disjoint Set Union.

In this approach, we iterate over each pair of points, and if the euclidean distance between them is less than or equal to ‘K’, we will group them together. To group the points effectively, we will use a disjoint set union. 

 

Algorithm:

  • Declare findGroup(i,’ GROUPS’) it will return the group number of point at ith index.
    • If GROUP[i] is equal to i,return i.
    • Else, Set GROUP[i] = findGroup(GROUP[i]) and return GROUP[i].

 

  • Declare unionn(i , j , ’GROUPS’, ’SIZES’)
    • Set a = findGroup(i)
    • Set b = findGroup(j)
    • If a is not equal to b,do the following:
      • If SIZES[a] < SIZES[b],(Size Compression)
        • Swap a and b.
      • Set GROUP[b] as a.
      • Set SIZES[a] as SIZES[a] + SIZES[b].
  • Declare distance(a,b) which will return the distance between point a and b.
    • Return square root of ( (a[0]-b[0])2 + (a[1]-b[1])2 ).
  • Declare ‘GROUPS’ array to store the group number of each point.
  • Declare ‘SIZES’ array to store the number of points in group i.
  • For each index i in the range from 0 to ‘N’-1, do the following:
    • Set GROUP[i] as i.
    • Set SIZES[i] as 1.
  • For each index i in the range from 0 to ‘N’-1, do the following:
    • For each index j in the range from i+1 to ‘N’-1, do the following:
      • If the distance between POINTS[i] and POINTS[j] is less than or equal to ‘K’:
        • Group them together as unionn(i,j, ’GROUPS’ SIZES).
  • Declare a variable ‘ANS’ to store the number of groups.
  • For each index i in the range from 0 to N-1, do the following:
    • If GROUP[i] is equal to i:
      • Set ‘ANS’ as ‘ANS’+1. (Found a new group)
  • Return ‘ANS’.
Time Complexity

O(N^2), where ‘N’ is the number of points in 'POINTS'.

 

In this approach, we are iterating over all pairs of points, and there are a total of N*(N-1) such pairs. Hence the overall time complexity is O(N^2).

Space Complexity

O(N), where ‘N’ is the number of points in 'POINTS'.

 

In this approach, we are using GROUP and SIZES arrays of size N to store the group number and group size. Hence the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Group Points
Full screen
Console