973. K Closest Points to Origin

Q: Heap or quickselect — which scores higher?

Both score equally. Heap is safer and demonstrates the top-K pattern. Quickselect shows selection-algorithm fluency. Default to heap unless the interviewer explicitly pushes you toward quickselect.

Q: Why squared distance instead of Euclidean?

sqrt is monotonic. Comparing squared distances yields the same ordering as comparing actual distances, but skips a per-comparison sqrt call. On 10^4 points that adds up.

mediumAsked at Robinhood

Given an array of points and integer k, return the k closest points to the origin. Robinhood asks the top-K family to test whether you reach for a max-heap of size k versus sort, and whether you cite the squared-distance optimization unprompted.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-19

Source citations

Public interview reports confirming this problem appears in Robinhood loops.

Glassdoor (2026-Q1)— Robinhood SWE-II onsite reports include K Closest as a recurring 30-minute round.
Blind (2025-12)— Robinhood backend SWE trip reports mention top-K problems as a thematic favorite.

Problem

Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0). The distance is Euclidean. You may return the answer in any order. The answer is guaranteed to be unique (except for the order it is in).

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: Squared distance: 1+9=10 vs 4+4=8. (-2,2) is closer.

Example 2

Input

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

Output

[[3,3],[-2,4]]

Approaches

1. Sort by squared distance

Sort the array by xi^2 + yi^2 and take the first k.

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

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

Tradeoff: Easy to read but does more work than needed. Use as the verbal warm-up before pivoting to heap or quickselect.

2. Max-heap of size k

Push each point's squared distance. When heap size exceeds k, pop the max. Heap contents are the answer.

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

class MaxHeap {
  constructor() { this.data = []; }
  push(v) { this.data.push(v); this._up(this.data.length - 1); }
  pop() { const top = this.data[0]; const last = this.data.pop(); if (this.data.length) { this.data[0] = last; this._down(0); } return top; }
  size() { return this.data.length; }
  _up(i) { while (i > 0) { const p = (i - 1) >> 1; if (this.data[p][0] >= this.data[i][0]) break; [this.data[p], this.data[i]] = [this.data[i], this.data[p]]; i = p; } }
  _down(i) { const n = this.data.length; while (true) { const l = 2*i+1, r = 2*i+2; let best = i; if (l < n && this.data[l][0] > this.data[best][0]) best = l; if (r < n && this.data[r][0] > this.data[best][0]) best = r; if (best === i) break; [this.data[best], this.data[i]] = [this.data[i], this.data[best]]; i = best; } }
}

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

Tradeoff: O(n log k) beats sort when k << n. The standard top-K pattern. Safer to implement under interview pressure than quickselect.

3. Quickselect (optimal average)

Partition the array around a pivot's squared distance. Recurse only into the side containing the kth element.

Time: O(n) average, O(n^2) worst
Space: O(1)

function kClosestQuick(points, k) {
  function dist(p) { return p[0]*p[0] + p[1]*p[1]; }
  function partition(lo, hi) {
    const pivot = dist(points[hi]);
    let i = lo;
    for (let j = lo; j < hi; j++) {
      if (dist(points[j]) <= pivot) {
        [points[i], points[j]] = [points[j], points[i]];
        i++;
      }
    }
    [points[i], points[hi]] = [points[hi], points[i]];
    return i;
  }
  let lo = 0, hi = points.length - 1;
  while (lo < hi) {
    const p = partition(lo, hi);
    if (p === k) break;
    if (p < k) lo = p + 1;
    else hi = p - 1;
  }
  return points.slice(0, k);
}

Tradeoff: Average O(n) — best on paper. Worst-case O(n^2) on bad pivots; mitigate with a random pivot. More careful coding than heap.

Robinhood-specific tips

Robinhood interviewers want to hear the three-way comparison out loud: 'Sort is O(n log n). Heap is O(n log k). Quickselect is O(n) average.' Then pick. Heap is the safest under time pressure. Always compute squared distance, not actual Euclidean — sqrt is monotonic, so it doesn't change ordering but it does slow the inner loop down measurably.

Common mistakes

Computing Math.sqrt — wastes time and risks float precision.
Over-sorting at the end when the problem says any order is fine.
Picking quickselect under time pressure and bugging the partition; choose heap unless you've practiced quickselect recently.

Follow-up questions

An interviewer at Robinhood may pivot to one of these next:

Top K Frequent Elements (LC 347).
K Closest in a stream — you can only store top-k.
K Closest Points in 3D — Euclidean generalization.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Heap or quickselect — which scores higher?

Both score equally. Heap is safer and demonstrates the top-K pattern. Quickselect shows selection-algorithm fluency. Default to heap unless the interviewer explicitly pushes you toward quickselect.

Why squared distance instead of Euclidean?

sqrt is monotonic. Comparing squared distances yields the same ordering as comparing actual distances, but skips a per-comparison sqrt call. On 10^4 points that adds up.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →