K Closest Points to Origin
Medium · Heap & Counting · Array · Math · Divide and Conquer · Geometry · Sorting · Heap (Priority Queue) · Quickselect
Problem
You are given a list of points on a plane, each one [x, y], and an integer k. Return the k points closest to the origin (0, 0), measured by straight-line (Euclidean) distance, √(x² + y²).
The points may be returned in any order. The tests never have a tie for the last place, so the set of k points is always unique. A point listed twice is two points, and both can be in the answer.
Examples
Input: points = [[1,3],[-2,2]], k = 1 Output: [[-2,2]]
(1, 3) is √10 from the origin and (-2, 2) is √8, so (-2, 2) is the closer one.
Input: points = [[3,3],[5,-1],[-2,4]], k = 2 Output: [[3,3],[-2,4]]
The squared distances are 18, 26 and 20. The two smallest are 18 and 20. [[-2,4],[3,3]] is also accepted.
Constraints
- 1 <= k <= len(points) <= 10^4
- -10^4 <= x, y <= 10^4
- the answer is unique: no two different points tie for the k-th place
Approaches
- Sort every point by distance — time O(n log n), space O(n)
Related problems
Start free on Cariara · Coding problems · System design studio
