Given a list of points on a plane, where the plane is a 2-D array with (x, y) coordinates, find the k closest points to the origin 0,0.

1-k-closest-points-to-0.js

export function kClosest(points, k) {
  const heap = new MaxHeap();

  // put initial k points into max heap with their distances
  // now we have largest distance seen so far at the top
  for (let i = 0; i < k; ++i) {
    const distance = getDistance(points[i]);
    heap.offer([distance, points[i]]);
  }

  // iterate the rest of points
  for (let i = k; i < points.length; ++i) {
    const distance = getDistance(points[i]);
    // if distance is smaller than the largest seen so far (top of the heap)
    // then largest seen so far is removed from the heap
    // and distance is added
    if (distance < heap.peek()[0]) {
      heap.poll();
      heap.offer([distance, points[i]]);
    }
  }

  // after iterating, we have k closest points in the heap
  const result = [];
  while (heap.size() > 0) {
    const [_, point] = heap.poll();
    result.push(point);
  }

  return result;
}

function getDistance(point) {
  return Math.sqrt(point.x * point.x, point.y * point.y);
}

2-README.md