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

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

Tested only

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

Which pattern gave this away within 90 seconds?
What changed from the standard template?
What would break the current solution?