Heap / Priority Queue
LC #973Medium
K Closest Points to Origin
Heap / Priority Queue
AmazonMetaGoogleBloombergProblem
Return the k closest points to the origin (0, 0). Distance is Euclidean.
arrayheapmathquickselect
Constraints
- ›1 ≤ k ≤ points.length ≤ 10⁴
- ›-10⁴ ≤ xi, yi ≤ 10⁴
Example
Input
points = [[1,3],[-2,2]], k = 1Output
[[-2, 2]]Why
dist([1,3])=√10, dist([-2,2])=√8. [-2,2] is closer.