We have a list of points on the plane. Find the K closest points to the origin (0, 0).
(Here, the distance between two points on a plane is the Euclidean distance.)
You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in.)
Example 1:
Input: points = [[1,3],[-2,2]], K = 1 Output: [[-2,2]] Explanation: The distance between (1, 3) and the origin is sqrt(10). The distance between (-2, 2) and the origin is sqrt(8). Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin. We only want the closest K = 1 points from the origin, so the answer is just [[-2,2]].
Example 2:
Input: points = [[3,3],[5,-1],[-2,4]], K = 2 Output: [[3,3],[-2,4]] (The answer [[-2,4],[3,3]] would also be accepted.)
Note:
1 <= K <= points.length <= 10000-10000 < points[i][0] < 10000-10000 < points[i][1] < 10000
class Solution {
public int[][] kClosest(int[][] points, int K) {
}
}
Idea - 1
Sort by distance from origin and take the first K points. Time
and space 
.
class Solution {
public int[][] kClosest(int[][] points, int K) {
int n = points.length;
Arrays.sort( points, new Comparator<int[]>()
{
public int compare(int[] a, int[] b)
{
return dist(a)-dist(b);
}
});
int[][] sol = new int[K][2];
for(int i = 0; i < K; ++i)
{
sol[i] = points[i];
}
return sol;
}
private int dist(int[] p)
{
return p[0]*p[0] + p[1]*p[1];
}
}
Runtime: 26 ms, faster than 69.27% of Java online submissions for K Closest Points to Origin.
Memory Usage: 54.7 MB, less than 92.47% of Java online submissions for K Closest Points to Origin.Idea - 2
Let's take the first K points as a solution candidate. (K+1)-th point can be added to the solution if it improves the situation, therefore, if it is closer to origin than the worst in current solution set. So, keeping a max heap and whenever it has size > K removing the worst would give us the closest K in the end. Time
and space .
class Solution {
public int[][] kClosest(int[][] points, int K) {
int n = points.length;
PriorityQueue<int[]> maxq = new PriorityQueue<int[]>(new Comparator<int[]>()
{
public int compare(int[] a, int[] b)
{
return dist(b)-dist(a);
}
});
for(int[] p : points)
{
maxq.offer(p);
if(maxq.size() > K)
{
maxq.poll();
}
}
int[][] sol = new int[K][2];
int i = 0;
while(!maxq.isEmpty())
{
sol[i++] = maxq.poll();
}
return sol;
}
private int dist(int[] p)
{
return p[0]*p[0] + p[1]*p[1];
}
}
Runtime: 35 ms, faster than 55.95% of Java online submissions for K Closest Points to Origin.
Memory Usage: 63 MB, less than 23.78% of Java online submissions for K Closest Points to Origin.Idea - 3
We can sort the distances and collect K of the ones that are less or equal to K-th in the sorted distance. Time and space .
class Solution {
public int[][] kClosest(int[][] points, int K) {
int n = points.length;
int[] dist = new int[n];
for(int i = 0; i < n; ++i)
{
dist[i] = dist(points[i]);
}
Arrays.sort(dist);
int Kth = dist[K-1];
int[][] sol = new int[K][2];
int j = 0;
for(int i = 0; i < n && j < K; ++i)
{
if(dist(points[i]) <= Kth)
{
sol[j++] = points[i];
}
}
return sol;
}
private int dist(int[] p)
{
return p[0]*p[0] + p[1]*p[1];
}
}
Runtime: 15 ms, faster than 80.58% of Java online submissions for K Closest Points to Origin.
Memory Usage: 67.3 MB, less than 5.04% of Java online submissions for K Closest Points to Origin.Idea - 4
We can use partitioning idea from quick sort and as soon as the partition is the one we want (the pivot is the K-th in sorted order) we are done. Worst case time is
, however average case is 
. Worst case stack space is and average case stack space is 
.
class Solution {
private static final Random rng = new Random(System.currentTimeMillis()%Integer.MAX_VALUE);
public int[][] kClosest(int[][] points, int K) {
int n = points.length;
int[] dist = new int[n];
for(int i = 0; i < n; ++i)
{
dist[i] = dist(points[i]);
}
partition(dist, 0, n-1, K);
int Kth = dist[K-1];
int[][] sol = new int[K][2];
int j = 0;
for(int i = 0; i < n && j < K; ++i)
{
if(dist(points[i]) <= Kth)
{
sol[j++] = points[i];
}
}
return sol;
}
private void partition(int[] A, int lo, int hi, int K)
{
if(lo > hi)
{
return;
}
int pi = lo+rng.nextInt(hi-lo+1);
int pivot = A[pi];
int i = lo-1, j = hi, k = lo;
while(k <= j)
{
if(A[k] < pivot)
{
swap(A, ++i, k++);
}
else if(A[k] > pivot)
{
swap(A, k, j--);
}
else
{
++k;
}
}
// j-th is the K-th element in the array
if(K==j+1)
{
return;
}
else if(K<j+1)
{
partition(A, lo, j-1, K);
}
else
{
partition(A, j+1, hi, K);
}
}
private void swap(int[] A, int i, int j)
{
int tmp = A[i];
A[i] = A[j];
A[j] = tmp;
}
private int dist(int[] p)
{
return p[0]*p[0] + p[1]*p[1];
}
}
Runtime: 8 ms, faster than 92.25% of Java online submissions for K Closest Points to Origin.
Memory Usage: 60.9 MB, less than 47.54% of Java online submissions for K Closest Points to Origin.
programmingpuzzles 