Problem

Submissions

Hints & solutions

Discuss

K Closest Points To Origin

Moderate

0/80

Average time to solve is 25m

Contributed by

7 upvotes

Asked in companies

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 )

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.

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

Hint 1

Hint 2

Think of a solution by sorting the points according to their distances from the origin.

Approaches (2)

Approach 1

Approach 2

Sorting

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)

Time Complexity

O(N * log N), where ‘N’ is the total number of points.

In the worst case, the sorting of the points takes O(N * log N) time.

Space Complexity

O(1).

In the worst case, constant space is required.

(100% EXP penalty)

K Closest Points To Origin

Console