Solution to Leetcode problem 973 K Closest Points to Origin

In this Leetcode problem (first problem of contest 119), we are given a list of points and a number K, and we have to return the K closest points to the origin.

Problem statement

Note that we are given the (x,y) coordinates of each points, and the coordinates are integers. Since we use euclidian distance sqrt(x^2+y^2) and sqrt doesn’t change the order, we can simply sort the points according to the values of x*x + y*y.

We can do so by using Arrays.parallelSort(T[] a, Comparator<? super T> cmp) . According to the documentation, you can provide a Comparator to sort elements in a custom way. Then we will only need to return the first K elements.

First we need to instantiate the comparator we want:

Comparator<int[]> c = 
    (int[] a, int[] b) -> 
        (a[0]*a[0] + a[1]*a[1])  - (b[0]*b[0] + b[1]*b[1]);

A comparator should return a positive value when the first value a is greater than b, so I always verify that this is the case mentally.

Now that we have a comparator, we apply the sort:

Arrays.parallelSort(points, c);

Then we only need to return the K first elements for points :

return Arrays.copyOfRange(points, 0, K);

This is the entire code:

class Solution {
    public int[][] kClosest(int[][] points, int K) {
        Comparator<int[]> c = 
            (int[] a, int[] b) -> 
                (a[0]*a[0] + a[1]*a[1])  - (b[0]*b[0] + b[1]*b[1]); 
        Arrays.parallelSort(points, c);
        return Arrays.copyOfRange(points, 0, K);
    }
}