Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

K Closest Points To Origin

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
5 upvotes
Asked in companies
AppleFacebookAmazon

Problem statement

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?
Detailed explanation ( Input/output format, Notes, Images )
Constraints:
1 <= T <= 10
1 <= K <= N <= 10 ^ 4 
-10 ^ 4 <= POINTS[i][0], POINTS[i][1] <= 10 ^ 4

Time limit: 1 sec.
Sample Input 1:
2
4 2
2 4 -2 2 1 1 3 -2
1 1
5 5
Sample Output 1:
-2 2 1 1
5 5
Explanation for sample 1:
For the first test case, the distances of the points from the origin are sqrt(20), sqrt(8), sqrt(2), and sqrt(13) respectively. So, the 2 closest points are at a distance of sqrt(2) and sqrt(8) respectively. So, the points are (1, 1) and (-2, 2).

For the second test case, the only point (5, 5) is at a distance of sqrt(50). Hence, the point is (5, 5).
Sample Input 2:
2
2 2
3 5 2 10
5 3
1 2 -2 2 3 0 0 -2 4 5
Sample Output 2:
2 10 3 5
-2 2 0 -2 1 2
Explanation for sample 2:
For the first test case, the distances of the points from the origin are sqrt(34) and sqrt(104) respectively. So, the 2 closest points are (2, 10) and (3, 5).

For the second test case, the distances of the points from the origin are sqrt(5), sqrt(8), sqrt(9), sqrt(4), and sqrt(41) respectively. So, the 3 closest points are at a distance of sqrt(4), sqrt(5), and sqrt(8) respectively. So, the points are (-2, 2), (0, -2) and (1, 2).
Full screen
Console