The points nearest the origin
Pick the k points closest to the origin from a long list, by keeping a max-heap of the k closest points seen so far and removing the farthest whenever it grows. About 16 minutes.
A max-heap for the k smallest
This is the top-k pattern again, but you want the k smallest distances. The worst kept point is the one with the biggest distance, so it must be the first to leave when a better point arrives.
A max-heap keeps its biggest key on top. Put each point in with its squared distance as the key, and when the heap grows past k, remove the top.
d = x * x + y * y heapq.heappush(heap, (-d, -x, -y))
(1, 3) has squared distance 10. The heap holds it.
A fixed order for ties
Several points can be at the same distance. To make the answer unique, the heap key is the whole triple: squared distance, then x, then y, each compared in turn. Two different points never have equal triples.
With Python's min-heap, store the negated triple so the largest triple is on top. After the pass, sort the survivors by the triple, so the closest comes first, and return the points.
items = [(-d, -x, -y) for d, x, y in heap] res = sorted(items)
Why compare squared distances instead of distances?
- AThey give the same order, without square roots or rounding
- BSquared values are always smaller
- CA heap needs squared values
Show the answer
They give the same order, without square roots or rounding. The square root increases with its input, so the order is unchanged.
K closest points to the origin
Given an array points where points[i] = [x, y] is a point on the plane, and an integer k, return the k points closest to the origin (0, 0) by Euclidean distance. List them from the closest to the farthest. If two points are at the same distance, the one with the smaller x comes first, and if x is also equal, the one with the smaller y. It is guaranteed that k does not exceed the number of points.
points = [[1, 3], [-2, 2], [5, 1]], k = 2 → [[-2, 2], [1, 3]]
1 ≤ k ≤ number of points ≤ 10,000 · -1,000 ≤ x, y ≤ 1,000