The K Closest Points to Origin#

We have a list points of points on the plane. We need to 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 of the coordinates.

Example#

Solution#

/**
 * @param {number[][]} points
 * @param {number} K
 * @return {number[][]}
 */
var kClosest = function(points, K) {
    const n = points.length;
    if(K >= n) return points;
    points.sort((a,b) => {
        const v1 = Math.pow(a[0], 2) + Math.pow(a[1], 2);
        const v2 = Math.pow(b[0], 2) + Math.pow(b[1], 2);
        return v1 - v2;
    })
    return points.slice(0, K);
};

Idea#

If we really want to calculate the Euclidean distance, the result might be a decimal. Besides the precision error, it's not as efficient as the integer calculation, and since the calculation is only for comparison, we can directly take the square of the Euclidean distance for the calculation. So we just need to sort the points based on the distance and take the first N elements. Of course, using a min or max heap for getting the first N smallest or largest values would be more efficient. First, we define n as the number of points. If K is greater than or equal to the number of points, we simply return the original array. Then we define the sort function, which calculates the square of the Euclidean distance between points a and b and sorts the points based on this value. After sorting, we use the slice method of the array to take the first K elements.

Daily Problem#

Reference#