K Closest Points to Origin

The problem

Array of points[i] = [xi, yi]. Return the k closest to origin. Distance = Euclidean; order of answer doesn’t matter. Ties: any of the tied points.

points = [[1,3],[-2,2]], k = 1 → [[-2,2]]

Compare squared distances x²+y² to avoid Math.sqrt.

Brute: sort all

function kClosestSort(points: number[][], k: number): number[][] {
  return [...points]
    .sort((a, b) => a[0] ** 2 + a[1] ** 2 - (b[0] ** 2 + b[1] ** 2))
    .slice(0, k);
}

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

Fine for many interviews.

Heap of size k (max-heap by distance)

Keep k closest; if a new point is closer than the farthest in the heap, replace.

function dist2(p: number[]) {
  return p[0] * p[0] + p[1] * p[1];
}

// simple max-heap via sort for clarity in small k — or binary heap
function kClosestHeap(points: number[][], k: number): number[][] {
  // max-heap as array of points; root = farthest among candidates
  const heap: number[][] = [];

  const siftUp = (i: number) => {
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (dist2(heap[i]) <= dist2(heap[p])) break;
      [heap[i], heap[p]] = [heap[p], heap[i]];
      i = p;
    }
  };
  const siftDown = (i: number) => {
    const n = heap.length;
    while (true) {
      let b = i;
      const l = i * 2 + 1;
      const r = l + 1;
      if (l < n && dist2(heap[l]) > dist2(heap[b])) b = l;
      if (r < n && dist2(heap[r]) > dist2(heap[b])) b = r;
      if (b === i) break;
      [heap[i], heap[b]] = [heap[b], heap[i]];
      i = b;
    }
  };

  for (const p of points) {
    if (heap.length < k) {
      heap.push(p);
      siftUp(heap.length - 1);
    } else if (dist2(p) < dist2(heap[0])) {
      heap[0] = p;
      siftDown(0);
    }
  }
  return heap;
}

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

Quickselect (average O(n))

Partition on distance like quicksort; stop when pivot index is k. Worth naming for FAANG follow-ups; careful with worst-case O(n²) unless randomized.

function kClosestQuick(points: number[][], k: number): number[][] {
  const d = (p: number[]) => p[0] * p[0] + p[1] * p[1];
  let lo = 0;
  let hi = points.length - 1;
  const target = k - 1;

  while (lo <= hi) {
    const pivot = d(points[hi]);
    let i = lo;
    for (let j = lo; j < hi; j++) {
      if (d(points[j]) <= pivot) {
        [points[i], points[j]] = [points[j], points[i]];
        i++;
      }
    }
    [points[i], points[hi]] = [points[hi], points[i]];
    if (i === target) break;
    if (i < target) lo = i + 1;
    else hi = i - 1;
  }
  return points.slice(0, k);
}

Edge cases

• k = n
• Duplicate distances
• Negative coords
• Origin itself [0,0]

Common mistakes

• Using sqrt and float noise
• Min-heap of all n then pop k (O(n + k log n) ok, but size-k max-heap is cleaner for memory)
• Mutating input without permission (quickselect)

Interview delivery

1. Squared distance.
2. Sort first.
3. Heap O(n log k) or quickselect.
4. Implement one solidly.
5. Complexities.

Related

• Top K Frequent Elements
• Find Median from Data Stream
• Kth Smallest in BST
• Two Sum
• JavaScript Interview Guide

Further reading

• LeetCode 973 — K Closest Points to Origin
• Quickselect