MediumReturn the k points nearest to (0,0) — by sorting or with a size-k max-heap.
Given an array of points where points[i] = [xi, yi] on the plane and an integer k, return the k points closest to the origin (0, 0). The distance between two points is the Euclidean distance. You may return the answer in any order.
Walkthrough
try:
Distance to the origin (0,0). We compare squared distance d = x² + y² (no square root needed).
For each point compute its squared distance d = x² + y². We compare d directly — taking the square root would not change the order.
Intuition
Closeness is measured by distance to the origin, √(x² + y²). Since the square root is increasing, comparing the squared distance x² + y² gives the same ordering — and avoids floating-point math.
Simplest approach: compute every squared distance, sort the points by it, and take the first k. That is O(n log n) — easy and often fast enough.
When n is huge but k is small, you do not need a full sort. Keep a max-heap of only the k best seen so far: the farthest of your current keepers sits on top.
For each new point, push it; if the heap now holds more than k, pop the top (the farthest). Whatever stays is the k closest — in O(n log k) time and O(k) space.
The algorithm
01Compute each point’s squared distance d = x² + y² to the origin.
02Sorting: sort all points by d ascending and return the first k.
03Heap: push each point onto a max-heap keyed by d.
04If the heap grows past size k, pop the top (the farthest point).
05After all points, the heap (or the first k of the sorted list) holds the answer.
Reference implementations
1 · Sort by distance — O(n log n)
Pair each point with its squared distance, sort ascending, and take the first k. The shortest code; great default.
1
function kClosest(points, k) {
2
// Pair each point with its squared distance, sort ascending, take the first k.
3
const withDist = points.map(([x, y]) => [x * x + y * y, x, y]);
4
withDist.sort((a, b) => a[0] - b[0]);
5
const result = [];
6
for (let i = 0; i < k; i++) {
7
result.push([withDist[i][1], withDist[i][2]]);
8
}
9
return result;
10
}
2 · Max-heap of size k — O(n log k)
Hold only the k best seen so far. Push each point; if the heap exceeds k, pop the farthest. Faster than sorting when k is much smaller than n.
1
function kClosest(points, k) {
2
// Keep at most k points; the heap's max (farthest) is dropped when we exceed k.
3
const heap = new MaxHeap(); // ordered by distance
4
for (const [x, y] of points) {
5
const d = x * x + y * y;
6
heap.push([d, x, y]);
7
if (heap.size() > k) {
8
heap.pop(); // remove the farthest
9
}
10
}
11
return heap.toArray().map(([d, x, y]) => [x, y]);
12
}
Complexity
Time
Sort: O(n log n). Heap: O(n log k) — better when k ≪ n. (QuickSelect: O(n) average.)