Find nearest k points from the central point The task:


  Given a list of points, a central point, and an integer k, find the
  nearest k points from the central point.
  
  For example, given the list of points [(0, 0), (5, 4), (3, 1)], the
  central point (1, 2), and k = 2, return [(0, 0), (3, 1)].


My solution:

const lst = [[0, 0], [5, 4], [3, 1]];
const center = [1, 2];
const k = 2;

const findNearestPoints = ({lst, center, k}) =&gt; {
  // I assume the data are valid; no error checks
  const calcHypo = x =&gt; Math.sqrt((x[0] - center[0])**2
                                + (x[1] - center[1])**2);
  const sortPoints = (a,b) =&gt; calcHypo(a) - calcHypo(b);
  return lst
   .sort(sortPoints)
   .slice(0,k);
};

console.log(findNearestPoints({lst, center, k}));
Don't sqrt the distance.

It is a common mistake when filtering distances to use the complete distance calculation.

Given 2 values a and b, if a &lt; b then it is also true that sqrt(a) &lt; sqrt(b). Hence you don't need the expensive sqrt calculation to know the if a point is closer than another.

To find the closest the following does not use the sqrt of the distance.

function closestPoint(points, point, dist){
    var x, y, found, min = dist * dist; // sqr distance
    for(const p of points) {
        x = p[0] - point[0];
        y = p[1] - point[1];
        x *= x;
        y *= y;
        if(x + y &lt; min){
            min = x + y;
            if (min === 0) { return p } // early exit
            found = p;
        }
    }
    return found;

}


Not in the sort!!!

You are doing the distance calculation in the sort DON'T!!!, that means you repeat the same calculations over and over.

To improve you throughput the following will reduce the over all time. The improvement is linear and does not change the complexity.

Note that in JS a ** 2 is slightly slower than a * a

A more efficient version of your solution

function findNearestPoints({list, center, k}) {
    const res = [];
    const cx = center[0], cy = center[1]; // alias and reduce indexing overhead
    const distSqr = (x, y) =&gt; (x -= cx) * x + (y -= cy) * y;
    const sort = (a, b) =&gt; a[1] - b[1];

    for (const p of list) { res.push([p, distSqr(p[0], p[1])]) }
    res.sort(sort).length = k;
    return res.map(p =&gt; p[0]);
}


The ** operator for roots

Note that JS has the ** operator. That you can use it to get roots by making the right side the inverse, 1 over the power. Thus the sqrt is **(1/2) the cube root is **(1/3)

eg 

if 2 ** 2 === 4 then 4 ** (1/2) === 2
if 2 ** 3 === 8 then 8 ** (1/3) === 2  Don't approximate 8 ** 0.33 !== 2
if 2 ** 4 === 16 then 16 ** (1/4) === 2


Better sort

The sort is the bottle neck in this problem.

You can use a binary tree sort as it is the least complex for real numbers (every coder should learn how to implement a binary tree sort)

Do you need the sort?

However I think (think means might be, I am going by instinct) that there is a faster solution that does not involve a sort and that is at most \$O(n)\$

Remember that the order of the points is not important, that you need only separate the points in two. It may take a few passes to do, but as long as the number of passes is not related to the number of points or 'k' you will have a \$O(n)\$ solution.

I am not going to give you the solution this time (if there is one) as there is no problem solving experienced gained coping code.