Skip to main content

973. K Closest Points to Origin

mediumAsked at Atlassian

K Closest Points to Origin is Atlassian's canonical heap-introduction problem. Given an array of points and an integer k, return the k points closest to (0,0) by Euclidean distance. Atlassian uses it as the first step toward more complex top-k ranking systems in their search UI.

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

Source citations

Public interview reports confirming this problem appears in Atlassian loops.

  • Glassdoor (2026-Q1)— Atlassian SWE-II onsite reports cite K Closest Points as the warm-up heap problem before Top K Frequent Elements.
  • Blind (2025-11)— Atlassian onsite threads mention K Closest Points as a recurring heap/quickselect problem.

Problem

Given an array of points where points[i] = [x_i, y_i] 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 <= x_i, y_i <= 10^4

Examples

Example 1

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

Explanation: sqrt(10) > sqrt(8), so (-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 distance, take first k

Sort the entire array by squared distance and slice the first k.

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

Tradeoff: Easiest to write; works for the LeetCode constraints. Wasteful when k << n because you do extra sort work for points you'll never return. Ship this as the warm-up, then move to heap.

2. Max-heap of size k (optimal when k << n)

Maintain a max-heap of size k. Push the first k points; for each remaining, if its distance < heap.peek().distance, pop the max and push the new point. Result = whatever stays in the heap.

Time
O(n log k)
Space
O(k)
class MaxHeap {
  constructor() { this.h = []; }
  size() { return this.h.length; }
  peek() { return this.h[0]; }
  push(v) {
    this.h.push(v);
    let i = this.h.length - 1;
    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;
    }
  }
  pop() {
    const top = this.h[0];
    const last = this.h.pop();
    if (this.h.length) {
      this.h[0] = last;
      let i = 0;
      for (;;) {
        const l = 2 * i + 1;
        const r = 2 * i + 2;
        let m = i;
        if (l < this.h.length && this.h[l][0] > this.h[m][0]) m = l;
        if (r < this.h.length && this.h[r][0] > this.h[m][0]) m = r;
        if (m === i) break;
        [this.h[i], this.h[m]] = [this.h[m], this.h[i]];
        i = m;
      }
    }
    return top;
  }
}
function kClosest(points, k) {
  const heap = new MaxHeap();
  for (const p of points) {
    const d = p[0] * p[0] + p[1] * p[1];
    if (heap.size() < k) {
      heap.push([d, p]);
    } else if (d < heap.peek()[0]) {
      heap.pop();
      heap.push([d, p]);
    }
  }
  return heap.h.map(([, p]) => p);
}

Tradeoff: True O(n log k) — better than sort when k << n. Atlassian's preferred answer. Use squared distance (no sqrt) — sqrt is monotonic, so ordering is unchanged and you skip a floating-point op per comparison.

3. Quickselect (best average, no extra structure)

Partition around a random pivot until pivot index = k. Returns the k closest in unspecified order in O(n) average time.

Time
O(n) average, O(n^2) worst case
Space
O(log n) recursion
function kClosestQuickselect(points, k) {
  const dist = (p) => p[0] * p[0] + p[1] * p[1];
  const partition = (lo, hi) => {
    const pivotIdx = lo + Math.floor(Math.random() * (hi - lo + 1));
    const pivot = dist(points[pivotIdx]);
    [points[pivotIdx], points[hi]] = [points[hi], points[pivotIdx]];
    let store = lo;
    for (let i = lo; i < hi; i++) {
      if (dist(points[i]) < pivot) {
        [points[store], points[i]] = [points[i], points[store]];
        store++;
      }
    }
    [points[store], points[hi]] = [points[hi], points[store]];
    return store;
  };
  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: Best average performance and zero extra memory if you can mutate the input. The worst-case is O(n^2) — random pivot mitigates but doesn't eliminate. Mention this as 'and there's a quickselect variant' at Senior+; SWE-II rounds usually stop at the heap.

Atlassian-specific tips

Atlassian interviewers always ask 'why don't you take the square root of the distance?'. Answer: 'sqrt is monotonic so it doesn't change ordering, and skipping it saves a float op per compare'. That's the question being graded — they want you to recognize the algebraic shortcut. After heap they often follow up with 'what if the points stream in and you only ever want the live top-k?' which is the same heap, just an online flavor.

Common mistakes

  • Computing sqrt(x*x + y*y) — works but you lose ~2x performance and the interviewer will ask why.
  • Building the heap as min-heap of size n then popping k — that's O(n + k log n) which is worse than max-heap of size k for the typical k << n case.
  • Forgetting to handle k > points.length — the LeetCode constraint guarantees k <= n but the streaming variant does not.

Follow-up questions

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

  • Streaming version — points arrive one-by-one; return the current top-k after each insert. Same heap.
  • Top K Frequent Elements (LeetCode 347) — same heap pattern keyed on count instead of distance.
  • What if the distance metric were Manhattan instead of Euclidean? Replace x*x + y*y with abs(x) + abs(y); algorithm unchanged.

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 at Atlassian?

Heap is the expected answer. Quickselect is a bonus only if you can explain the worst-case risk. At SWE-II/SWE-III the heap closes the question; mention quickselect as 'and there's an O(n) average variant' to score on the breadth axis without spending time on it.

Why max-heap and not min-heap?

You want to keep the k SMALLEST distances. A max-heap of size k lets you compare each new point to the current MAX of your kept set — if the new point is smaller, evict the max. Min-heap would force you to keep all n in the heap.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →