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

Question

The problem is, given a list of coordinates, determine the number of k coordinates that are closest to the origin.

I have been able to determine the distance between the points and origin, however when filtering for the closest k points, I am lost. I decided to place this logic in a the second for loop, sort the array of distance from closest to furthest, and push the values that are less than K.

function kClosest(points, k) {
    let length = [];
    let arr = [];
    let result = [];
    let a = 0;
    let b = 0;

    for (let i = 0; i < points.length; i++) {
        a = points[i][0]; //x coord
        b = points[i][1]; //y coord (y will always be second number or '1')
        length.push(parseFloat(calcHypotenuse(a, b).toFixed(4)))
        arr.push([points[i], length[i]])
    }

    function calcHypotenuse(a, b) {
        return (Math.sqrt((a * a) + (b * b)));
    }

    for (let i = 0; i < k; i++) {
        arr = arr.sort();
        result.push(arr[i][0])
    }
    return result;
}



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

Expected output: [-5, 4], [4, 6] // I had [-5, 4], [-6, -5]

Answer 1

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

Answer 2

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.