In this problem we are given a list of points, and we are supposed to calculate the K number of closest points to the origin. For example if we are given a set of 10 points, and a K value of 4, we need to return 4 points which are closest among the given list of points. Or if we have 4 points as shown below, the K closest if K = 2 would be green and blue, assuming red and yellow are further from the origin.
This problem becomes very easy if we know the Kth point. The Kth point or the Kth distance is the final point. The furthest among our 4 points from the origin.
To accomplish this we calculate the distance of each point and sort them. Once we get the sorted array of distances, finding the Kth distance is as easy as getting the Kth index value.
Once we get this value we compare this value with each distance, and for all the points whose distance is lower than this Kth Distance, we add in our result array which we simply return in the end giving us our answer. This would look like:
public int[][] kClosest(int[][] points, int K) {
int length = points.length;
int [] distances = new int [length];
for(int i = 0; i < length; i ++){
distances[i] = distance(points[i]);
} Arrays.sort(distances);
int KthDistance = distances[K-1]; int [][] result = new int [K][2];
int i = 0;
for(int j = 0; j<length; j++){
if( distance(points[j]) <= KthDistance){
result[i++] = points[j];
}
} return result;
}public int distance(int [] point){
return point[0]*point[0] + point[1]*point[1];
}
Video Explanation:
