K Closest Points to Origin
K Closest Points to Origin is LeetCode 973 (Medium). You get an array points, where points[i] = [xᵢ, yᵢ] is a point on a plane, and an integer k. Return the k points closest to the origin (0, 0), using ordinary straight-line (Euclidean) distance.
- The answer may be returned in any order, and it is unique apart from order.
- There are 1 to 10⁴ points, with coordinates between −10⁴ and 10⁴.
- 1 <= k <= points.length <= 10⁴
- -10⁴ <= xi, yi <= 10⁴
Intuition
Two ideas make this fast.
- Skip the square root: the distance is √(x² + y²), but you only ever compare two distances. A bigger x² + y² always means a bigger root, so comparing x² + y² gives the same order with exact whole numbers.
- Keep only k candidates: hold the k closest points seen so far in a max-heap, which keeps the farthest of them on top. When a new point makes it k + 1, the top is the one point that cannot be among the k closest, so it comes out.
After every point has passed through, the heap holds exactly the k closest points to origin.
"The k smallest, largest or closest of n items" calls for a heap of size k that keeps the worst survivor on top; this k closest points LeetCode problem is the classic example. Kth Largest Element in an Array (215) and Top K Frequent Elements (347) use the same pattern with a min-heap, because there the worst survivor is the smallest.
Approach
Before reading on, take [[3,3],[5,-1],[-2,4]] with k = 2. Which point has to go, and which single comparison tells you?
Two ways to solve it
Push each point by its score and pop the farthest whenever the heap holds k + 1.
- Speed: each heap step costs log k, not log n.
- Memory: only k + 1 points at a time.
- Streams: works when points arrive one by one.
The answer interviewers look for.
Sort all the points by x² + y² and return the first k.
- Code: two lines in Python.
- Speed: orders every point, not just the k closest.
- Memory: the sort may need a copy of the array.
Fine as a first answer; slower when k is small.
The heap only ever orders k + 1 points, so it beats a full sort whenever k is smaller than n. The steps, code and live demo below follow the heap; the sorting code comes after the demo.
Score each point by x² + y²
For a point (x, y) compute x * x + y * y. It ranks points exactly like the true distance, so it is all the comparison needs. With coordinates up to 10⁴ the largest score is 2 × 10⁸, which still fits in a 32-bit integer.
Push the point into a max-heap
In the k closest points Python code, heapq is a min-heap, so push the score as a negative number, (-score, x, y); the farthest point then sits on top. C++'s priority_queue is already a max-heap, and Java needs a comparator that puts larger scores first.
Pop the top when there are k + 1
If the heap now holds k + 1 points, pop the top. It is the farthest of those k + 1, so k points are closer than it and it can never be in the answer. The heap never grows past k + 1, which is where the log k comes from.
Return what is left
After the last point the heap holds exactly k points, the closest ones. The problem accepts any order, so read them straight out of the heap without sorting.
K Closest Points to Origin solution in Python | C++ | Java
Sort by squared distance
Sort the points by x² + y², nearest first, and return the first k of them.
Common pitfalls
Taking the square root
d = math.sqrt(x * x + y * y)
d = x * x + y * y
It gives the same order at extra cost, and it turns an exact whole-number comparison into a floating-point one.
Popping before pushing
if len(heap) == k:
heapq.heappop(heap)
heapq.heappush(heap, (-d, x, y))heapq.heappush(heap, (-d, x, y))
if len(heap) > k:
heapq.heappop(heap)Popping first throws out the farthest held point before the new one is compared with it. If the new point is even farther, it stays and a closer point is lost.
Complexity
K Closest Points to Origin FAQ
Can K Closest Points to Origin be solved in O(n)?
On average, yes, with quickselect: partition the points around a pivot score until the k closest sit at the front, recursing into one side only. It averages O(n) but can degrade to O(n²) with bad pivots, while the heap guarantees O(n log k).