973. K Closest Points to Origin

mediumAsked at Bloomberg

Bloomberg's geo-analytics tools identify the K nearest branch offices or client locations to a reference point — this problem tests whether you apply a max-heap of size K for a clean O(n log K) solution instead of sorting the entire dataset when K is small.

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

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.

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] is sqrt(10); distance of [-2,2] is sqrt(8). The closer point 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

Sort all points by squared Euclidean distance, then slice the first k. Simple, O(n log n).

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

function kClosest(points, k) {
  const dist = ([x, y]) => x*x + y*y;
  return points.sort((a, b) => dist(a) - dist(b)).slice(0, k);
}

Tradeoff:

2. Max-heap of size K (optimal for large n, small k)

Maintain a max-heap of the k closest points seen so far, keyed by squared distance. For each new point, if it is closer than the heap maximum, replace the max. The heap never exceeds size k, giving O(n log k).

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

class MaxHeap {
  constructor() { this.data = []; }
  push([dist, pt]) {
    this.data.push([dist, pt]);
    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;
  }
  peek() { return this.data[0]; }
  size() { return this.data.length; }
  _up(i) {
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.data[i][0] > this.data[p][0]) {
        [this.data[i], this.data[p]] = [this.data[p], this.data[i]]; i = p;
      } else break;
    }
  }
  _down(i) {
    const n = this.data.length;
    while (true) {
      let b = i, l = 2*i+1, r = 2*i+2;
      if (l < n && this.data[l][0] > this.data[b][0]) b = l;
      if (r < n && this.data[r][0] > this.data[b][0]) b = r;
      if (b === i) break;
      [this.data[i], this.data[b]] = [this.data[b], this.data[i]]; i = b;
    }
  }
}

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

Tradeoff:

Bloomberg-specific tips

Bloomberg asks this in analytics and data-platform interviews. The sorting solution is perfectly fine when n is small, but mention the O(n log k) max-heap approach and state when it wins: when n is very large and k is small, you avoid processing the tail of the sorted array entirely. Also note the squared-distance optimization — omitting sqrt() avoids floating-point and is O(1) faster per comparison. Bloomberg engineers are expected to call out micro-optimizations like this in code review.

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 Bloomberg interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →