49. K Closest Points to Origin
You are given an array points where points[i] = [x, y] is a point on the plane, and an integer k. Return the k points that are closest to the origin (0, 0), measured by ordinary (Euclidean) distance sqrt(x² + y²).
You may return the points in any order. The test data guarantees the answer is unique: the k-th closest point is strictly closer than the (k+1)-th, so there is never a tie at the cut-off. The same coordinates can appear more than once; each copy is a separate point.
Input: points = [[3,4],[1,-1],[-2,2]], k = 1 Output: [[1,-1]]
Explanation: The squared distances are 25, 2 and 8, so [1,-1] is the closest.
Input: points = [[5,0],[-1,-1],[2,2],[0,-3]], k = 2 Output: [[-1,-1],[2,2]]
Explanation: Squared distances 25, 2, 8, 9: the two smallest are 2 and 8. [[2,2],[-1,-1]] would also be accepted.
Input: points = [[0,0]], k = 1 Output: [[0,0]]
Constraints
1 <= k <= points.length <= 10^4-10^4 <= x, y <= 10^4- The answer is unique (no tie at the
k-th distance)
Follow-up: If the points arrive as an endless stream and you must always be able to report the current k closest, which of the approaches still works?
💡 Hint 1
You never need the actual square root: comparing x² + y² orders the points the same way.
💡 Hint 2
Sorting all points by distance works in O(n log n). To do better, keep only the best k seen so far in a max-heap keyed by distance, evicting the farthest when it grows past k.
💡 Hint 3
Quickselect on the distances finds the cut-off in O(n) on average, if you want to avoid the heap altogether.
Try it yourself first ✎
Solutions stick better after a real attempt. Peek when you're ready.
Approach
Compare points by squared distance x² + y² (no square roots needed). Scan the points while keeping a max-heap of at most k points, ordered so the farthest kept point sits on top. Push each point; whenever the heap holds k + 1 points, pop the top, which discards the farthest candidate. After the scan the heap contains exactly the k closest points. Each push or pop costs O(log k). JavaScript has no built-in priority queue, so the JS solution includes a small binary heap.
function kClosest(points, k) {
const dist = ([x, y]) => x * x + y * y;
const heap = new Heap((a, b) => dist(a) > dist(b)); // farthest kept point on top
for (const p of points) {
heap.push(p);
if (heap.size > k) heap.pop();
}
return heap.items;
}
// Minimal binary heap. higher(a, b) is true when a belongs closer to the top than b.
class Heap {
constructor(higher) {
this.items = [];
this.higher = higher;
}
get size() {
return this.items.length;
}
peek() {
return this.items[0];
}
push(x) {
const a = this.items;
a.push(x);
let i = a.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (!this.higher(a[i], a[p])) break;
[a[i], a[p]] = [a[p], a[i]];
i = p;
}
}
pop() {
const a = this.items;
const top = a[0];
const last = a.pop();
if (a.length) {
a[0] = last;
let i = 0;
while (true) {
const l = 2 * i + 1;
const r = l + 1;
let m = i;
if (l < a.length && this.higher(a[l], a[m])) m = l;
if (r < a.length && this.higher(a[r], a[m])) m = r;
if (m === i) break;
[a[i], a[m]] = [a[m], a[i]];
i = m;
}
}
return top;
}
}class Solution {
public int[][] kClosest(int[][] points, int k) {
// Max-heap by squared distance: the farthest kept point is on top.
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(dist(b), dist(a)));
for (int[] p : points) {
heap.offer(p);
if (heap.size() > k) heap.poll();
}
return heap.toArray(new int[0][]);
}
private static int dist(int[] p) {
return p[0] * p[0] + p[1] * p[1];
}
}No submissions yet. Press Submit to run your code against every test.
/**
* @param {number[][]} points
* @param {number} k
* @return {number[][]}
*/
function kClosest(points, k) {
}Run your code to see results here.