K Closest Points to Origin

Medium

Problem

Given points [x, y], return the k points closest to the origin by Euclidean distance, in any order.

Example 1

Input:  points = [[3,3], [5,-1], [-2,4]], k = 2
Output: [[3,3], [-2,4]]

Test cases

Case 1

Input:    [[1,3],[-2,2]], 1
Expected (any order): [[-2,2]]

Case 2

Input:    [[3,3],[5,-1],[-2,4]], 2
Expected (any order): [[3,3],[-2,4]]

Case 3

Input:    [[0,1],[1,0]], 2
Expected (any order): [[0,1],[1,0]]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution2 approaches

1. Sort by distance

Time O(n log n)Space O(n)

Sort by x² + y² (no square root needed) and take k.

const kClosest = (points, k) =>
points.sort((a, b) => a[0] ** 2 + a[1] ** 2 - (b[0] ** 2 + b[1] ** 2)).slice(0, k);

2. Max-heap of size k

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

Keep the k closest so far; the root is the farthest of them and gets evicted when a closer point arrives. MinHeap is the class from the patterns page with a reversed comparator.

function kClosest(points, k) {
const d = ([x, y]) => x * x + y * y;
const heap = new MinHeap((a, b) => d(b) - d(a)); // max-heap by distance
for (const p of points) {
heap.push(p);
if (heap.size > k) heap.pop();
}
return heap.a;
}

Quickselect gives O(n) average if asked for better than n log k.