K Closest Points to Origin
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]]
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.