K Closest Points to Origin
Problem Statement
Given an array points, where points[i] = [xi, yi], and an integer k, return the k points closest to the origin [0,0]. The answer may be returned in any order.
Input
A list of 2D points points and an integer k.
Output
A list of k points with the smallest distances to the origin, in any order.
Constraints
- •
1 <= k <= points.length <= 10000 - •
-10000 <= xi, yi <= 10000
Examples
Example 1
points = [[1,3],[-2,2]], k = 1
[[-2,2]]Example 2
points = [[3,3],[5,-1],[-2,4]], k = 2
[[3,3],[-2,4]]Learning Objectives
- Recognise closest k as a top-k problem where smaller distance is better.
- Use squared distance to avoid unnecessary square roots.
- Choose a size-k max-heap so the farthest retained point is easy to evict.
- Explain why output order is irrelevant for this problem.
Intuition
Pattern Recognition
The signal is k closest, which means we are selecting the best k candidates by a scoring function. Here the score is distance to the origin, and smaller is better. For fixed-size top-k where smaller scores win, keep a size-k max-heap so the root is the worst retained candidate.
The trap is computing actual Euclidean distance with a square root. Square root preserves ordering, so comparing x^2 + y^2 is enough. Another trap is using a min-heap and popping the closest points too early; for a fixed-size heap you want the farthest retained point at the root so it can be evicted.
Common mistakes
- ×Calling square root for every point even though squared distance preserves the same ordering.
- ×Using a min-heap of size k and accidentally removing the closest retained point.
- ×Sorting all points when a size-k heap gives O(n log k).
- ×Returning only distances instead of the original point coordinates.
Algorithm Explanation
Key idea
Order points by squared distance x^2 + y^2. Keep a max-heap of at most k points, where the root is the farthest point currently retained. After pushing each point, if the heap is too large, pop the root. That removes the worst retained point and leaves the k closest candidates seen so far.
Heap walkthrough
Use points = [[1,3],[-2,2],[5,8],[0,1]] and k = 2. Squared distances are 10, 8, 89, and 1. See [1,3], heap becomes [10:[1,3]]. See [-2,2], heap becomes [10:[1,3],8:[-2,2]], with distance 10 at the root because this is a max-heap. See [5,8], push to get [89:[5,8],8:[-2,2],10:[1,3]], then pop [5,8] because it is farthest. See [0,1], push to get [10:[1,3],8:[-2,2],1:[0,1]], then pop [1,3]. The retained points are [-2,2] and [0,1].
Algorithm
- Create a max-heap of points ordered by squared distance.
- For each point, compute priority as x^2 + y^2 through the comparator.
- Push the point into the heap.
- If the heap size exceeds k, pop the farthest retained point.
- Poll the remaining points into the answer array.
Solutions
Solution: Size-k max-heap by squared distance
Use this when k may be much smaller than n and you want to avoid sorting all points.
A smaller distance is better, so the fixed-size heap should expose the largest distance among retained points. Push each point, and when the heap exceeds k, evict the farthest root.
Step-by-step
- Build a PriorityQueue whose comparator makes larger squared distance come first.
- Offer each point from points.
- If the heap grows beyond k, poll the farthest retained point.
- After the scan, the heap contains exactly the k closest points.
- Poll them into a result matrix and return it.
O(n log k)
O(k)
Each point performs heap work against a heap capped at k + 1 points.
Java implementation
Dry Run
Sample input
points = [[1,3],[-2,2],[5,8],[0,1]], k = 2. Track the max-heap by squared distance.
| step | point | squared distance | heap after push | heap after trim |
|---|---|---|---|---|
| 1 | [1,3] | 10 | [10:[1,3]] | [10:[1,3]] |
| 2 | [-2,2] | 8 | [10:[1,3],8:[-2,2]] | [10:[1,3],8:[-2,2]] |
| 3 | [5,8] | 89 | [89:[5,8],8:[-2,2],10:[1,3]] | [10:[1,3],8:[-2,2]] |
| 4 | [0,1] | 1 | [10:[1,3],8:[-2,2],1:[0,1]] | [8:[-2,2],1:[0,1]] |
After all points are scanned, the heap contains the two smallest squared distances, 8 and 1, so the answer can be [[-2,2],[0,1]].
Interview Tips
Emphasise the direction of the heap: because smaller distance is better, the fixed-size heap is a max-heap that exposes the farthest retained point. Also say that squared distance is enough; avoiding square root is both faster and less error-prone.
Likely follow-ups
- How would you solve it with quickselect for average O(n) time?
- What if the points arrive as a stream and k closest must be maintained online?
- How would you break ties deterministically by x coordinate and then y coordinate?
- How would the distance function change for Manhattan distance?
Similar Problems
Key Takeaways
- For k closest with smaller score better, use a size-k max-heap.
- Squared distance preserves ordering and avoids square root.
- The heap root is the farthest retained point, so it is the candidate to evict.
- Output order does not matter unless the statement requires it.