Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumheap-top-k quick-select

K Closest Points to Origin

Problem (restated)

Given points on a plane and integer k, return the k points closest to (0,0). Order among answers may vary.

Intuition

Track the k nearest with a max-heap keyed by squared distance (avoid sqrt).

Approaches

Max-heap of size k

Unverified

Time O(n log k)Space O(k)

Idea. Push each point; if heap size > k, pop farthest. Remaining heap is the answer multiset.

Walkthrough. [[1,3],[-2,2]], k=1 → [[-2,2]].

Trade-offs. Full sort is O(n log n); heap wins when k ≪ n. Quickselect is average O(n).

Solution

export function kClosest(points: number[][], k: number): number[][] {
  // max-heap of size k by distance
  const heap: number[][] = [];
  const dist = (p: number[]) => p[0]! * p[0]! + p[1]! * p[1]!;
  for (const p of points) {
    heap.push(p);
    heap.sort((a, b) => dist(b) - dist(a));
    if (heap.length > k) heap.shift();
  }
  return heap;
}

export function kClosest(points: number[][], k: number): number[][] {
  // max-heap of size k by distance
  const heap: number[][] = [];
  const dist = (p: number[]) => p[0]! * p[0]! + p[1]! * p[1]!;
  for (const p of points) {
    heap.push(p);
    heap.sort((a, b) => dist(b) - dist(a));
    if (heap.length > k) heap.shift();
  }
  return heap;
}

Template connection

Classic top-k via bounded max-heap.

Reflection

Squared distance is enough. A square root does not change the order. A max-heap of size k drops the farthest point.
On a tie, which point you keep is free. k == n returns every point. k == 1 returns the nearest.
(0, 0) has distance 0. Squaring a negative coordinate drops the sign.