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.
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) |