Last Updated: 28 Mar, 2021
K-Closest Points
Moderate
Asked in companies
You are given an array of points of size ‘n’. such that point[i]=[xi, yi] where 'xi' is coordinate and 'yi' is y coordinate of the 'ith' point. You need to find 'k' closest points from the origin (0,0).
The distance between two points ('x1', 'y1') and ('x2', 'y2') is given as (x1-x2)^2 +(y1-y2)^2.
If two points have the same distance then the one with minimum 'x' coordinate will be chosen.
Input Format:
The first line of input contains an integer ‘T’ denoting the number of test cases.
The first line of the test case consists of two integers ‘n’ indicating a number of points and 'k'.
The next line ‘n’ lines consist of 2 space-separated integers 'xi' and 'yi', such that 'xi' is x-coordinate and 'yi' is y-coordinate of the 'ith' point.
Output Format:
Return the list of 'k' points. Return the list in ascending order of distance from the origin. Such that the one with minimum distance will be first. If two points have the same distance then one with a minimum x-coordinate will be first.
Print the output of each test case in a separate line.
Constraints:
1 <= ’T ’<= 10
1 <= ’n’ <= 10^6
1 <= ’k’ <= ’n’
-10^6 <= xi, yi <= 10^6
Follow Up:
Can you solve the problem in time complexity better than O(NlogN)?
Approaches
This approach is similar to quick sort. Using this approach, we will try to sort the first K element in their respective places.
We have created a function quickSelection(points, l, r, k), where points are the given array, k is the given integer, l and r is the current range in which we are trying to sort the elements.
During partition, we have selected the last element as the pivot element. We will try to find the correct position of the pivot element, and we will return the pivot index.
Algorithm:
- Create a function partition(points, left, right)
- Set pivot as points[right] and partitionIndex as left
- Iterate i from left to right
- Set value1 as points[i][0] * points[i][0] + points[i][1] * points[i][1] and value2 as pivot[0] * pivot[0] + pivot[1] * pivot[1]
- Check if value1 is less than value2
- Swap points[i] and points[partitionIndex]
- Increment partitionIndex by 1
- Otherwise check if value1 is equal to value2 and points[i][0] is less than pivot[0].
- Swap points[i] and points[partitionIndex]
- Increment partitionIndex by 1
- Swap arr[partitionIndex] and arr[right]
- Return the variable partitionIndex
- Create a function quickSelect(points, l, r, k)
- We will iterate till l is less than or equal to r
- Set mid as partition(points, l, r)
- Check if mid is equal to k
- We will return from the function
- Check if mid is less than k.
- Set l as mid + 1
- Otherwise, set r as mid - 1.
- We will iterate till l is less than or equal to r
- Create a recursive call to quickSelect(points, 0, n - 1, k)
- Maintain an array answer and insert the first k elements in the array answer.
- Return the array answer.
The main idea is to sort the points according to the distance and the conditions.
The algorithm is as follows:
- Sort the points array using the custom comparator.
- In custom comparator, if the distance of first is equal to the distance of the second point then return x1<x2. Such that if x1 is less than x2 then the first point will come first else second will come first.
- IF distance is not the same then return distance1<distance2 Such that if distance1 is less than distance2 then the first point will come first else second will come first.
- Select the first ‘k’ points and return it.
The main idea is to use max priority queue then extract the topmost k elements.
The top of the priority queue will store point with maximum distance and maximum x-coordinate among the maximum distance.
The algorithm is as follows:
- First, push first ‘k’ points in the max priority queue ‘pq’.
- After that run a loop from k+1 to n.If the distance of the ith point is less than the top point present in ‘pq’ then pop the topmost element and push the ith point. If the distance is the same and the ith point has a minimum x coordinate then also pop the top element and push the ith element.
- If the above conditions are not true then move to the next point.
- In the end, return the k points in ‘pq’.