K Closest Points To Origin

Posted: 16 Jan, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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.
Approach 1

Steps:

  1. 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.
  2. 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):

  1. Return (point1[0] ^ 2 + point1[1] ^ 2) <= (point2[0] ^ 2 + point2[1] ^ 2)
Try Problem