K Closest Points to Origin
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

Question

K Closest Points to Origin

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.

Accepted Answer

As we need to find K closest restaurants to the source (0,0), I used priority queue(MaxHeap) in python to eliminate all the farthest restaurants and have only k closest restaurants left at the end of the loop.

I had stored the elements in priority Queue as a pair [distance, coordinates], so that at I can directly get the coordinates for the k closest restaurants to return in the result.

Accepted Answer

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)

Space Complexity: O(1)Explanation:

O(1).

In the worst case, constant space is required.

Time Complexity: O(nlogn)Explanation:

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.

Accepted Answer

Heap

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:
1. Find the distance of the current point from the origin.
2. Push this point to the heap as {distance, i}.
3. 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:
1. 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}.
2. Then add points[index] to the res array.
3. Remove the point from the heap.
Finally, return the res array.

Space Complexity: OtherExplanation:

O(K), where ‘K’ is the given number.

In the worst case, the size of the heap is O(K) as at any point we are storing a maximum of ‘K’ points in the heap.

Time Complexity: OtherExplanation:

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

In the worst case, we will be traversing the whole input array of points and push the point to the heap. Since there can be a maximum of ‘K’ number of points in the heap, so the time required to push a point to the heap is log K. Hence, the overall time complexity is O(N * log K).

Note:

For Example:

Follow Up:

Input format:

Output format:

Note:

Constraints:

Top Jio Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Jio Software Developer