Find the K closest points to the origin (0, 0)

I suggest using a custom sort for this - you can pass Array.sort() a comparison function, like this:

function kClosest(points, k) {

    //sorts the array in place
    points.sort((point1, point2) => {
        const distanceFromOrigin1 = getDistanceFromOrigin(point1);
        const distanceFromOrigin2 = getDistanceFromOrigin(point2);

        //sort by distance from origin, lowest first
        return distanceFromOrigin1 - distanceFromOrigin2;
    });

    //returns first k elements
    return points.slice(0, k);
}

function getDistanceFromOrigin(point) {
    const [x, y] = point; //array destructuring
    return (x*x) + (y*y);
}

console.log(kClosest([
    [-5, 4],
    [-6, -5],
    [4, 6]
], 2))

See https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort for more details on custom sorting.


Sorting the whole array is wasteful, and may not even be possible. It is wasteful because the question didn't ask for a total ordering of all the elements, not even the k elements. Sorting using a comparison-based sort takes O(n log(n)) time. More generally, if the input is a stream of numbers, storing all of them in the memory and sorting them may not even be possible.

I don't know much about JavaScript, but on general algorithmic turf, we can solve this problem faster using one of the following 2 methods:

  1. Using a Max Priority Queue: Create a max PQ with an ordering based on the distance from the origin. Keep inserting the elements in the max PQ, and whenever the size exceeds k, remove the top element (the maximum). In the end, the PQ would have the k smallest elements. Space complexity: O(k), time complexity: O(n log(k)) which for k << n, may be close to O(n).
  2. Using Quick-select: Run quick-select k times on the input. This assumes the input fits in the memory (space O(n)), but runs in O(nk) time, which for k << n, may be close to O(n).