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]

Possible duplicate of [Finding the first n largest elements in an array](https://stackoverflow.com/questions/7272534/finding-the-first-n-largest-elements-in-an-array) — Redu, Feb 10 '19 at 19:32

score 5 · Answer 1 · answered Feb 07 '19 at 08:44

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:

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

Duncan Thacker · Accepted Answer · 2019-02-06T01:30:54.303

4

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.

edited Feb 06 '19 at 01:30

answered Feb 05 '19 at 23:23

Duncan Thacker

5,073
1
10
20

Hi Duncan, thanks for the suggestion. When I went to implement it, it halfway worked. The issue is my "arr" array. Since it holds both the points/coords and lengths of the points to the origin, when I pass arr into the sort function, I get the same result. However, when I simplify arr to containing just length[i], I get an array of sorted length values, which is nice, but how can I relate those sorted lengths back to the original coordinates? That's where I am at right now. – Tyler Morales Feb 06 '19 at 00:31
You don't really need to do that stuff any more - you can just directly sort the `points` array that gets passed in and there's no need to store lengths in a separate array. The length only gets calculated during the sort process (implemented as a `getDistanceFromOrigin()` function). – Duncan Thacker Feb 06 '19 at 00:34
To clarify, I'll expand my answer to include the full solution. – Duncan Thacker Feb 06 '19 at 00:34
There's a magic number 2 in the `return` statement and the comment above it. ;) – Roland Illig Feb 06 '19 at 01:26

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

2 Answers2