Heap / Priority Queue · 093Medium
K Closest Points to Origin
Given an array of points on the plane and an integer k, return the k points closest to the origin (0, 0) by Euclidean distance. Any order is acceptable.
Constraints
- 1 <= k <= points.length <= 10^4
- -10^4 <= xi, yi <= 10^4
Examples
kClosest([[1, 3], [-2, 2]], 1) -> [[-2, 2]] kClosest([[3, 3], [5, -1], [-2, 4]], 2) -> [[3, 3], [-2, 4]] // any order kClosest([[0, 0]], 1) -> [[0, 0]] kClosest([[1, 3], [-2, 2]], 2) -> [[-2, 2], [1, 3]] // k = n returns everything, any order kClosest([[-3, -4], [1, 1], [2, 2]], 2) -> [[1, 1], [2, 2]] // distances 25, 2, 8 kClosest([[1, 0], [0, 1]], 1) -> [[1, 0]] // a tie — either point is acceptable
Edge cases
- k equal to the point count returns everything.
- Negative coordinates are fine — squaring handles the sign.
Show the target complexity (spoiler)
- Naive
- O(n log n) time — sort every point by distance when only k are needed.
- Target
- O(n log k) with a size-k max-heap, or O(n) average with Quickselect on squared distance.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/13-heap-priority-queue/093-k-closest-points-to-origin.js ./practice c 093