Last Updated: 3 Sep, 2021

Group Points

Hard

Asked in company

Solve now

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)].

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

Solve now

Approaches

01 Approach

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 i^th 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])²+ (a[1]-b[1])² ).
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’.

Solve now

02 Approach

In this approach, we will first sort the ‘POINTS’ array based on x-coordinates, and recursively we will divide the points into two halves and group the points in the left half and right half. 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 i^th index.
- If GROUP[i] is equal to i,return i.
- Else, Set GROUP[i] = findGroup(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])²+ (a[1]-b[1])² ).

Declare a function brute(‘START’, ’END’ , POINTS, GROUPS, SIZES,’ K’) which will group the elements POINTS[START] to POINTS[END].
- For each index i in the range start to end, do the following:
  - For each index j in the range from i+1 to end:
    - If the distance of POINTS[i] and POINTS[j] is less than or equal to ‘K’:
      - Group them together as unionn(i,j, ’GROUPS’ SIZES).

Declare a function groupUtil(‘START’, ’END’, POINTS, GROUPS, SIZES,’ K’) to recursively group the points of that range.
- If END-START+1 is less than or equal to 3:
  - Call brute(‘START’, ’END’ , POINTS, GROUPS, SIZES,’K’) and return.
- Set MID as (‘START’ + ‘END’) /2.
- Call groupUtil(‘START’, MID-1, POINTS, GROUPS, SIZES,’ K’) for the left half.
- Call groupUtil(MID+1, END, POINTS, GROUPS, SIZES,’ K’) for the right half.
- Now we will try to group the points near the midline.
- Set LEFT as -1.(Leftmost point of the strip.)
- Set RIGHT as -1.(Rightmost point of the strip.)
- For each index i in the range from START to END, do the following:
  - If the distance between the x-coordinates of midpoint and POINTS[i]is less than or equal to ‘K’, then include it into the strip.
    - If LEFT is equal to -1, Set LEFT as i.
    - Set RIGHT as i.
- Call brute(‘LEFT’, ’RIGHT’ , POINTS, GROUPS, SIZES,’ K’) to group the points in that strip.
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.
Sort ‘POINTS’ according to the x-coordinate of points.
Call groupUtil(0, N-1, POINTS, GROUPS, SIZES,’ K’) to group all the points.
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’.

Solve now