K Closest Points to Origin
A ride-hailing app shows each rider the k nearest available drivers. Positions are measured on a grid centred on the rider, so the rider stands at (0, 0) and points[i] = [x, y] is the position of driver i. Distance is ordinary straight-line (Euclidean) distance, sqrt(x² + y²).
Return the k drivers closest to the rider, in any order. The tests make sure there is no tie at the cut-off: the k-th closest driver is always strictly closer than the next one. Two drivers can stand at the same coordinates; they are still separate points.
Input: points = [[4,-3],[1,1],[-2,5]], k = 1 Output: [[1,1]]
Explanation: The squared distances are 25, 2 and 29, so [1,1] is the closest driver.
Input: points = [[6,2],[-1,3],[0,-4],[2,2]], k = 3 Output: [[0,-4],[-1,3],[2,2]]
Explanation: The squared distances are 40, 10, 16, 8, so only [6,2] is left out. Any order of the three points is accepted.
Input: points = [[2,0],[2,0],[5,5]], k = 2 Output: [[2,0],[2,0]]
Explanation: Two drivers wait at the same spot, and both of them are returned.
Constraints
kis between 1 and the number of drivers, which is at most 10^4.- Every coordinate is an integer from -10^4 to 10^4.
- There is never a tie at the
k-th smallest distance.
Follow-up: If drivers keep coming online one at a time and the app must always know the current k nearest, which of these 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.