Skip to main content

26. K Closest Points to Origin

mediumAsked at Coinbase

Retrieve the K accounts with the smallest distance from a reference price level — Coinbase uses this heap problem to test real-time top-K selection, the engine behind their order-proximity ranking in the matching engine.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given an array of points where points[i] = [xi, yi] and an integer k, return the k points closest to the origin (0, 0). The distance is Euclidean. You may return the answer in any order — the answer is guaranteed to be unique.

Constraints

  • 1 <= k <= points.length <= 10^4
  • -10^4 <= xi, yi <= 10^4

Examples

Example 1

Input
points = [[1,3],[-2,2]], k = 1
Output
[[-2,2]]

Explanation: Distance of [1,3] = sqrt(10); [-2,2] = sqrt(8). Closest is [-2,2].

Example 2

Input
points = [[3,3],[5,-1],[-2,4]], k = 2
Output
[[3,3],[-2,4]]

Approaches

1. Sort by distance

Compute squared distance for each point, sort ascending, return first k. No sqrt needed since sqrt is monotone.

Time
O(n log n)
Space
O(n)
function kClosest(points, k) {
  return points
    .map(p => [p[0] * p[0] + p[1] * p[1], p])
    .sort((a, b) => a[0] - b[0])
    .slice(0, k)
    .map(([, p]) => p);
}

Tradeoff:

2. Max-heap of size k (optimal for streaming)

Maintain a max-heap of k nearest so far. For each new point, if its distance is less than the heap top, evict the top and insert the new point. Result is the heap contents.

Time
O(n log k)
Space
O(k)
class MaxHeap {
  constructor() { this.h = []; }
  push(item) {
    this.h.push(item);
    this._up(this.h.length - 1);
  }
  pop() {
    const top = this.h[0];
    const last = this.h.pop();
    if (this.h.length) { this.h[0] = last; this._down(0); }
    return top;
  }
  peek() { return this.h[0]; }
  get size() { return this.h.length; }
  _up(i) {
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.h[p][0] >= this.h[i][0]) break;
      [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
      i = p;
    }
  }
  _down(i) {
    const n = this.h.length;
    while (true) {
      let max = i, l = 2*i+1, r = 2*i+2;
      if (l < n && this.h[l][0] > this.h[max][0]) max = l;
      if (r < n && this.h[r][0] > this.h[max][0]) max = r;
      if (max === i) break;
      [this.h[max], this.h[i]] = [this.h[i], this.h[max]];
      i = max;
    }
  }
}

function kClosest(points, k) {
  const heap = new MaxHeap();
  for (const p of points) {
    const dist = p[0]*p[0] + p[1]*p[1];
    heap.push([dist, p]);
    if (heap.size > k) heap.pop();
  }
  return heap.h.map(([, p]) => p);
}

Tradeoff:

Coinbase-specific tips

Coinbase uses this to test whether you know when to prefer O(n log k) over O(n log n). In a live order stream with n >> k, maintaining a bounded heap is the right production choice — it is how they rank nearest-limit orders relative to mid-price in real time. Mention that squared distance avoids the sqrt call and that the max-heap approach also handles streaming input where n is not known upfront.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill K Closest Points to Origin and other Coinbase interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →