K Closest Points to Origin

1. Define the problem

Given an array of points on the X-Y plane and an integer k, return the k points closest to the origin (0, 0). You may return the answer in any order . Keep a max-heap of size k keyed by squared distance — no need for a square root. A point only earns a spot if it beats the farthest point currently kept.

Constraints

1 ≤ k ≤ points.length ≤ 10⁴
-10⁴ ≤ xi, yi ≤ 10⁴

Example

Inputpoints = [[1, 3], [-2, 2]], k = 1

Output[[-2, 2]]

Explanation (1, 3) has squared distance 10; (-2, 2) has squared distance 8, so it is closer.

2. Know the words first

In plain terms

Squared distance: x² + y² — comparing this instead of the true distance (which needs a square root) gives the same ordering, cheaper to compute.

3. Visualize the solution

Keep the k closest in a bounded max-heap

(3,3)18

(5,-1)26

Statusinit

k = 2, first two points fill the heap: (3, 3) dist 18, (5, -1) dist 26.

What happens in this step

push [18, (3,3)]  →  heap = [[18, (3,3)]]
push [26, (5,-1)]  →  sift up: 18 < 26, swap  →  heap = [[26, (5,-1)], [18, (3,3)]]

The heap is a max-heap keyed by squared distance, so the farthest of the two kept points — (5, -1) at 26 — rises to the root; it's the first to be evicted if a closer point shows up.

Step 1 of 3

Steps to visualize

For each point, compute its squared distance from the origin.
Push it into a max-heap capped at size k, keyed by that distance.
If the heap is full and the new point is closer than the farthest point kept, swap it in.
The heap ends up holding exactly the k closest points.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Keep the k closest in a bounded max-heap

(3,3)18

(5,-1)26

Statusinit

k = 2, first two points fill the heap: (3, 3) dist 18, (5, -1) dist 26.

What happens in this step

push [18, (3,3)]  →  heap = [[18, (3,3)]]
push [26, (5,-1)]  →  sift up: 18 < 26, swap  →  heap = [[26, (5,-1)], [18, (3,3)]]

The heap is a max-heap keyed by squared distance, so the farthest of the two kept points — (5, -1) at 26 — rises to the root; it's the first to be evicted if a closer point shows up.

Step 1 of 3

5. Solution

Solution

solution.tsTypeScript

function kClosest(points, k) {
  const heap = []; // entries stored as [distSq, point]

  function push(item) {
    heap.push(item);
    let i = heap.length - 1;
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (heap[parent][0] < heap[i][0]) {
        [heap[parent], heap[i]] = [heap[i], heap[parent]];
        i = parent;
      } else {
        break;
      }
    }
  }

  function siftDown() {
    let i = 0;
    const size = heap.length;
    while (true) {
      let largest = i;
      const left = 2 * i + 1;
      const right = 2 * i + 2;
      if (left < size && heap[left][0] > heap[largest][0]) largest = left;
      if (right < size && heap[right][0] > heap[largest][0]) largest = right;
      if (largest === i) break;
      [heap[i], heap[largest]] = [heap[largest], heap[i]];
      i = largest;
    }
  }

  for (const point of points) {
    const distSq = point[0] * point[0] + point[1] * point[1];
    if (heap.length < k) {
      push([distSq, point]);
    } else if (distSq < heap[0][0]) {
      heap[0] = [distSq, point];
      siftDown();
    }
  }

  return heap.map((entry) => entry[1]);
}

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

6. Test cases

Test cases

Input	Expected	Covers
`points = [[1, 3], [-2, 2]], k = 1`	`[[-2, 2]]`	example from the docstring
`points = [[3, 3], [5, -1], [-2, 4]], k = 2`	`[[3, 3], [-2, 4]]`	k selects the two closest of three candidates
`points = [[0, 0], [1, 1]], k = 1`	`[[0, 0]]`	a point exactly at the origin is always closest
`points = [[-5, 4], [-6, -1], [3, 3]], k = 2`	`[[3, 3], [-6, -1]]`	negative coordinates mixed with a clearly closer point
`points = [[2, 2]], k = 1`	`[[2, 2]]`	smallest valid input, a single point
`points = [[1, 1], [2, 2]], k = 2`	`[[1, 1], [2, 2]]`	k equals the total number of points, everything is returned

K Closest Points to Origin