Last Updated: 16 Jan, 2021
K Closest Points To Origin
Moderate
Asked in companies
Your house is located at the origin of a 2-D plane. You have 'N' neighbours who live at 'N' different points on the plane. You want to visit exactly 'K' different neighbours who live closest to your house, you are given a 2 - D matrix 'POINTS'. So, find out the coordinates of the neighbours you are going to visit. The answer is guaranteed to be unique.
Note:
The distance between two points on a plane is the Euclidean Distance.
For Example:
If N = 2, K = 1 and the points are {2,3}, {-1, 2}.
Then the distance of the first point from the origin is sqrt((2 - 0) ^ 2 + (3 - 0) ^ 2) = sqrt(13).
The distance of the second point from the origin is sqrt((-1 - 0) ^ 2 + (2 - 0) ^ 2) = sqrt(5).
Follow Up:
Can you solve this in O(N log K) time complexity?
Input format:
The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then, the 'T' test cases follow.
The first line of each test case contains two integers 'N' and 'K' separated by a single space.
The second line of each test case contains 2 * N space-separated integers where for each i = 1 to 'N', the (2 * i - 1) th and the (2 * i) th element represents the x-coordinate and y-coordinate of ith point respectively.
Output format:
For each test case, print a single line containing 2 * K space-separated integers where for each i = 1 to 'K', the (2 * i - 1) th and the (2 * i) th element represents the x-coordinate and y-coordinate of the i th point respectively. Print the output in sorted order.
The output of each test case will be printed in a separate line.
Note:
You do not need to print anything or sort the final result. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= K <= N <= 10 ^ 4
-10 ^ 4 <= POINTS[i][0], POINTS[i][1] <= 10 ^ 4
Time limit: 1 sec.
Approaches
Steps:
- Create a custom comparator function, say compare(point1, point2) to sort the array of points in the increasing order of their distances from the origin. Note that, the distance from the origin can be calculated by sqrt(x^2 + y^2), where x and y represent the x-coordinate and y-coordiante of the point respectively.
- Create an empty array of points to store the K closest points to the origin. Let’s call it res. Push the first K points of the input array into the res array and return it.
bool compare(point1, point2):
- Return (point1[0] ^ 2 + point1[1] ^ 2) <= (point2[0] ^ 2 + point2[1] ^ 2)
Instead of sorting all the points like in the previous approach, we create a custom heap of size K and push the distances of the points along with their index in the input array. Whenever the size of the heap exceeds K, we remove a point from the heap.
Steps:
- Create an empty array of points to store the K closest points to the origin. Let’s call it res.
- Create a custom heap of size K, that contains a pair of integers, with the first integer representing the distance of a point from the origin and the second integer representing its index in the input array.
- Run a loop from i = 0 to N - 1 and do:
- Find the distance of the current point from the origin.
- Push this point to the heap as {distance, i}.
- If the size of the heap exceeds K, then remove the top element from the heap.
- Then a run a loop from i = 0 to K-1 and do:
- Find the index of the top element of the heap, i.e. second parameter of the top element of the heap as we store the point in the form of {distance, i}.
- Then add points[index] to the res array.
- Remove the point from the heap.
- Finally, return the res array.