973. K Closest Points to Origin

Q: Why squared distance instead of Euclidean?

sqrt is monotonic — comparing squared distances gives the same ordering as comparing actual distances. Skip the sqrt to save computation.

Q: Heap or quickselect — which is preferred?

Both score equally. Heap is safer and shows the general top-K pattern. Quickselect shows you can implement selection. Heap is the default.

mediumAsked at Amazon

Given an array of points and integer k, return the k points closest to the origin (0, 0). Amazon asks this to test whether you reach for a max-heap of size k or quickselect — same pattern as top-K problems.

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

Source citations

Public interview reports confirming this problem appears in Amazon loops.

Glassdoor (2026-Q1)— Amazon SDE I/II onsite reports cite this as a recurring top-K problem.
Blind (2025-11)— Recurring Amazon interview problem.

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 between two points on the X-Y plane is the Euclidean distance. You may return the answer in any order. The answer is guaranteed to be unique (except for the order that 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]]

Example 2

Input

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

Output

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

Approaches

1. Sort by distance

Sort by squared distance, take 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. Often the expected first answer. Mention before heap/quickselect.

2. Max-heap of size k

Push each point's squared distance. When heap size > k, pop the max. Result is the heap contents.

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() { if (!this.data.length) return; 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) { while (true) { const l = 2*i+1, r = 2*i+2; let best = i; if (l < this.data.length && this.data[l][0] > this.data[best][0]) best = l; if (r < this.data.length && 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: Beats sort when k << n. Standard top-K pattern.

3. Quickselect (optimal average)

Partition points around a pivot's distance. Recurse only into the side containing the kth smallest.

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). Worst-case O(n^2) on bad pivots — mitigated by random pivot. Beats heap on average but more careful coding.

Amazon-specific tips

Amazon interviewers want you to articulate all three approaches and pick. State 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. Use squared distance to avoid sqrt — sqrt is monotonic so ordering is preserved.

Common mistakes

Using actual Euclidean distance (sqrt) — wastes computation. Squared distance suffices for comparison.
Forgetting that the answer can be in any order — over-sorting at the end.
Picking quickselect under time pressure and bugging the partition; heap is safer.

Follow-up questions

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

K Largest / Smallest in Stream — heap variants.
K Closest Points in 3D space (Euclidean generalization).
What if the points were given as a stream and you only stored top-k?

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why squared distance instead of Euclidean?

sqrt is monotonic — comparing squared distances gives the same ordering as comparing actual distances. Skip the sqrt to save computation.

Heap or quickselect — which is preferred?

Both score equally. Heap is safer and shows the general top-K pattern. Quickselect shows you can implement selection. Heap is the default.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →