MediumNeetCode150ArrayMathDivide and ConquerSortingHeap (Priority Queue)Geometry
K Closest Points to Origin
Return k closest points to origin.
Examples
Input
points = [[1,3],[-2,2]], k = 1
Output
[[-2,2]]
Distance: sqrt(10) vs sqrt(8). (-2,2) is closer.
Constraints
- •
1 <= k <= points.length <= 10^4 - •
-10^4 < x,y < 10^4
Approaches
Sort by distance.
CodeT: O(n log n) | S: O(n)
def kClosest(points, k):
return sorted(points,key=lambda p: p[0]**2+p[1]**2)[:k]Keep k closest.
CodeT: O(n log k) | S: O(k)
import heapq
def kClosest(points, k):
h=[]
for p in points:
heapq.heappush(h,(p[0]**2+p[1]**2,p))
if len(h)>k: heapq.heappop(h)
return [p for _,p in h]Average O(n).
CodeT: O(n) average | S: O(1)
Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Sort All | O(n log n) | O(n) | Sort by distance. |
| Min Heap Size K | O(n log k) | O(k) | Keep k closest. |
| Quickselect | O(n) average | O(1) | Average O(n). |
Sort All
T: O(n log n)S: O(n)
Sort by distance.
Min Heap Size K
T: O(n log k)S: O(k)
Keep k closest.
Quickselect
T: O(n) averageS: O(1)
Average O(n).
Common Mistakes
Wrong distance calc
Not using squared distance
Wrong k count