K Closest Points to Origin | Medium
Intuition:
- Calculate the distance, sort it then return the first K element
Gotchas:
- square root not necessary
Base cases:
- None
Solution:
class Solution:
def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
points.sort(key=lambda p:(p[0]**2 + p[1]**2))
return points[:K]
# Using
class Solution:
def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
heap = []
for p in points:
d = -(p[0]**2 + p[1]**2)
heapq.heappush(heap, (d,p))
if len(heap) > K:
heapq.heappop(heap)
return [p for d,p in heap]
Complexity Analysis:
O(N …
more ...