K Closest Points to Origin
- 1 min read
- LC-Medium
- Binary-heap
3 years ago
Solution
- Use a binary heap
- Go through each point, calculate the distance to origin, and a store a 3 value tuple in a list
- Heapify the list- remember, it is faster to heapify a whole list rather than heappush each time
- Heappop k times
| Time | Space | Explanation |
|---|---|---|
O(n) | O(n) |
def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
distances = []
for x, y in points:
dist = (x ** 2 + y ** 2) ** 0.5
distances.append((dist, (x, y)))
heapify(distances)
ans = []
while k:
ans.append(heappop(distances)[1])
k -= 1
return ans