K Closest Points to Origin
Find the k closest points to the origin using sorting vs a max-heap of size k.
K Closest Points to Origin
Problem: Given an array of points on a 2D plane and an integer k, return the k points closest to the origin (0, 0). Distance is measured using Euclidean distance.
Example:
- Input:
points = [[1,3],[-2,2]],k = 1 - Output:
[[-2,2]](distance² of [1,3] = 10, distance² of [-2,2] = 8 — so [-2,2] is closer)
Note
You don't need the actual distance — comparing x² + y² is enough. Skipping the square root avoids floating point and is faster.
How to Think About It
Starting point: Sort all points by distance, return the first k. O(n log n) — correct, but you're ranking every point when you only need to identify k of them.
The realization: Same "top-k" pattern as kth-largest, but now "better" means closer to origin. You want to maintain a running set of the k closest points seen so far.
The key question: What element do you evict from that set when a better candidate arrives? The farthest one — the one with the largest distance.
Why a max-heap (not min-heap)? You want the farthest of the current top-k at the root so you can compare and evict it in O(log k). If a new point is closer than the root, pop the root and push the new point. A max-heap keeps the worst candidate at the top — ready to be kicked out.
Optimization: Never compute sqrt(x² + y²). Comparing squared distances gives the same ordering and avoids floating point entirely.
Brute Force
View Brute Force
Optimal — Max-Heap of Size k
View Optimal Solution
| Approach | Time | Space |
|---|---|---|
| Sort all | O(n log n) | O(n) |
| Max-Heap of size k | O(n log k) | O(k) |