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:
- 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 thek
smallest elements. Space complexity:O(k)
, time complexity:O(n log(k))
which fork << n
, may be close toO(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 inO(nk)
time, which fork << n
, may be close toO(n)
.