Problem Understanding
Each points[i] = [xi, yi] is a point on a flat X-Y plane. Return the k of them that lie nearest to the origin (0, 0).
"Nearest" means straight-line (Euclidean) distance, which for a point measured from the origin is √(x² + y²). The k points can come back in any order.
Algorithm Strategy
We want the K smallest distances.
- We can use a Max-Heap of size K.
- Why Max-Heap? Because we want to keep the "smallest" K elements. If the heap gets too big (> K), we want to evict the largest element (the one furthest away) to make room for smaller ones.
Algorithm:
- Initialize a Max-Heap.
- Iterate through all points.
- Calculate squared distance for each point (
x^2 + y^2). We don't need sqrt since it preserves order. - Push (distance, point) to heap.
- If size > k, pop the max element.
- Return the points remaining in the heap.
Interactive Visualization
The plane shows every point. Once the heap holds k, a dashed circle passes through the farthest point kept — a new point has to land inside it to stay. The max-heap beside it is keyed by squared distance.
Dry Run
Points: [[3,3], [5,-1], [-2,4], [1,1], [0,-2]], k = 2
| Step | Point | x² + y² | Heap after push (root first) | Size > k? | Heap after |
|---|---|---|---|---|---|
| 1 | [3,3] |
18 | [18] |
No | [18] |
| 2 | [5,-1] |
26 | [26, 18] |
No | [26, 18] |
| 3 | [-2,4] |
20 | [26, 18, 20] |
Pop 26 | [20, 18] |
| 4 | [1,1] |
2 | [20, 18, 2] |
Pop 20 | [18, 2] |
| 5 | [0,-2] |
4 | [18, 2, 4] |
Pop 18 | [4, 2] |
Result: [[0,-2], [1,1]] — distances 4 and 2, in any order.
Edge Cases
- k = n: nothing is popped, and every point is returned.
- A point on the origin: its distance is 0, so it is never the farthest while other points are kept.
- Equal distances: LeetCode guarantees the answer is unique, so a tie never decides which points are returned.
- No square roots: comparing
x² + y²gives the same order as the true distance and stays in integers.
Solution
A max-heap of size k keyed by squared distance, in every language. JavaScript, TypeScript and C carry a small heap of their own.
K Closest Points to Origin Code
1class Heap {2 constructor(before) {3 this.items = [];4 this.before = before;5 }67 size() {8 return this.items.length;9 }1011 peek() {12 return this.items[0];13 }1415 push(item) {16 const a = this.items;17 a.push(item);18 let i = a.length - 1;19 while (i > 0 && this.before(a[i], a[(i - 1) >> 1])) {20 const parent = (i - 1) >> 1;21 [a[i], a[parent]] = [a[parent], a[i]];22 i = parent;23 }24 }2526 pop() {27 const a = this.items;28 const top = a[0];29 const last = a.pop();30 if (a.length > 0) {31 a[0] = last;32 let i = 0;33 while (true) {34 const left = 2 * i + 1, right = 2 * i + 2;35 let first = i;36 if (left < a.length && this.before(a[left], a[first])) first = left;37 if (right < a.length && this.before(a[right], a[first])) first = right;38 if (first === i) break;39 [a[i], a[first]] = [a[first], a[i]];40 i = first;41 }42 }43 return top;44 }45}4647var kClosest = function(points, k) {48 const heap = new Heap((a, b) => a[2] > b[2]);49 for (const [x, y] of points) {50 const dist = x * x + y * y;51 heap.push([x, y, dist]);52 if (heap.size() > k) {53 heap.pop();54 }55 }56 return heap.items.map(([x, y]) => [x, y]);57};