K-Closest Points

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
2 upvotes
Asked in companies
Rootstock SoftwareGoogle inc

Problem statement

You are given an array of points of size ‘n’. such that point[i]=[xi, yi] where 'xi' is coordinate and 'yi' is y coordinate of the 'ith' point. You need to find 'k' closest points from the origin (0,0).

The distance between two points ('x1', 'y1') and ('x2', 'y2') is given as (x1-x2)^2 +(y1-y2)^2.

If two points have the same distance then the one with minimum 'x' coordinate will be chosen.

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of the test case consists of two integers ‘n’ indicating a number of points and 'k'.

The next line ‘n’ lines consist of 2 space-separated integers 'xi' and 'yi', such that 'xi' is x-coordinate and 'yi' is y-coordinate of the 'ith' point.
Output Format: 
Return the list of 'k' points. Return the list in ascending order of distance from the origin. Such that the one with minimum distance will be first. If two points have the same distance then one with a minimum x-coordinate will be first.

Print the output of each test case in a separate line.
Constraints: 
1 <= ’T ’<= 10
1 <= ’n’ <= 10^6
1 <= ’k’ <= ’n’
-10^6 <= xi, yi <= 10^6
Sample Input 1:
2
4 3
1 1
-1 1
2 2
-2 2
4 4
1 0
2 0
3 0
4 0
Sample Output 1:
-1 1
1 1
-2 2
1 0
2 0
3 0
4 0
Explanation:
For first case The distance of the points from origin 
are :-
(1,1) => (1-0)^2+(1-0)^2=2
(-1,1) => (-1-0)^2 +(1-0)^2=2
(2,2)=>(2-0)^2+(2-0)^2=8
(-2,2)=>(-2-0)^2+(2-0)^2=8

Thus the answer will be in order
(-1,1) -> (1,1)->(-2,2)

The first two points have the same distance but the x coordinate of the second point is less. Hence the second point comes first.

For Second Case
(1,0) => (1-0)^2+(0-0)^2=1
(2,0) => (2-0)^2 +(0-0)^2=4
(3,0)=>(3-0)^2+(0-0)^2=9
(4,0)=>(4-0)^2+(0-0)^2=16

Thus the answer will be in order
(1,0) ->(2,0)->(3,0)->(4,0)
Sample Input 2:
2
4 2
2 5
4 4
5 1
4 2
4 4
4 4
3 3
4 3
1 2
Sample Output 2:
4 2
5 1
1 2
3 3
4 3
4 4
Hint

Try to use an approach similar to quick sort in this problem.

Approaches (3)
Quick Select

This approach is similar to quick sort. Using this approach, we will try to sort the first K element in their respective places.

 

We have created a function quickSelection(points, l, r, k), where points are the given array, k is the given integer, l and r is the current range in which we are trying to sort the elements.

 

During partition, we have selected the last element as the pivot element. We will try to find the correct position of the pivot element, and we will return the pivot index.

 

Algorithm:

 

  • Create a function partition(points, left, right)
    • Set pivot as points[right] and partitionIndex as left
    • Iterate i from left to right
      • Set value1 as points[i][0] * points[i][0] + points[i][1] * points[i][1] and value2 as pivot[0] * pivot[0] + pivot[1] * pivot[1]
      • Check if value1 is less than value2
        • Swap points[i] and points[partitionIndex]
        • Increment partitionIndex by 1
      • Otherwise check if value1 is equal to value2 and points[i][0] is less than pivot[0].
        • Swap points[i] and points[partitionIndex]
        • Increment partitionIndex by 1
    • Swap arr[partitionIndex] and arr[right]
    • Return the variable partitionIndex

     

  • Create a function quickSelect(points, l, r, k)
    • We will iterate till l is less than or equal to r
      • Set mid as partition(points, l, r)
      • Check if mid is equal to k
        • We will return from the function
      • Check if mid is less than k.
        • Set l as mid + 1
      • Otherwise, set r as mid - 1.

 

  • Create a recursive call to quickSelect(points, 0, n - 1, k)
  • Maintain an array answer and insert the first k elements in the array answer.
  • Return the array answer.
Time Complexity

O(n^2), where n is the number of points.
 

The partition index will be the last index in the range of indices, and we are iterating through the whole range to find the partition index, which will take O(n^2) time. Hence the overall time complexity is O(n^2). 

Space Complexity

O(n), where n is the number of points.
 

The recursion stack takes O(n) in the worst case. Hence the overall space complexity is O(n).

Code Solution
(100% EXP penalty)
K-Closest Points
Full screen
Console