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.)

In K Closest Points to Origin Algorithm by using Priority Queues in C++/Java, we have solved the problem by using a priority queue in C++/Java. This post will focus on solving the same problem using the custom sorting algorithm.

C++ Program to Compute K Closest Points to Origin using Custom Sorting Algorithm

C++’s sort method allows a third parameter as the custom comparator.

1
2
3
4
5
6
7
8
9
10
11

class Solution {
public:
    vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
        sort(begin(points), end(points), [](auto &a, auto &b) {
            auto d1 = a[0] * a[0] + a[1] * a[1];
            auto d2 = b[0] * b[0] + b[1] * b[1];
            return d1 < d2;
        });
        return vector(begin(points), begin(points) + K);
    }
};

class Solution {
public:
    vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
        sort(begin(points), end(points), [](auto &a, auto &b) {
            auto d1 = a[0] * a[0] + a[1] * a[1];
            auto d2 = b[0] * b[0] + b[1] * b[1];
            return d1 < d2;
        });
        return vector(begin(points), begin(points) + K);
    }
};

Then we can use the vector constructor (giving it two iterators start and finish) to return a copy of the vector.

Java Program to Compute K Closest Points to Origin using Custom Sorting Algorithm

In Java, we can use Arrays.sort method to sort the int[][] object. We can then use Arrays.copyOfRange to return a copy of the sub array (substring on Array).

1
2
3
4
5
6
7
8
9
10

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

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

Both implementations have O(N.LogN) time complexity which is what a sorting algorithm would cost nowadays.

–EOF (The Ultimate Computing & Technology Blog) —