Solutions to LeetCode 973 K Closest Points to Origin
LeetCode 973
K Closest Points to Origin (Medium) [link]
1] Python Sort. Sort the points by their Euclidean distances to the origin. Time complexity O(n log n). Space complexity O(log n) needed by sorting.
The .sort python function is based on the Time sort algorithm which was created by Tim peters. This particular soring algorithm is a hybrid sorting algorithm based on insertion and mergesort algorithms internally. The time complexity in best case is O(n), average case is O(n log n), worse case is O(n log n). The space complexity is O(n).
class Solution:
def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
points.sort(key = lambda x: x[0]**2 + x[1]**2)
return points[:k]
2] maxHeap. Because we are looking for the top k closest points to the origin, i.e. the k smallest distances. We need a max heap to store the k smallest distances. Whenever we add a distance into the heap, it will pop out the currently largest distance. The usefulness of maxHeap is that it can determine the current max/min and pop it out. In the end, what remains in the heap is the smallest k distances.
Time complexity O(n log k). Each pop or push operation take time O(log k). Space complexity O(n).
class Solution:
def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
q = [(-x ** 2 - y ** 2, i) for i, (x,y) in enumerate(points[:k])]
heapq.heapify(q)
n = len(points)
for i in range(k,n):
x, y = points[i]
dist = -x**2 - y**2
heapq.heappush(q, (dist,i))
heapq.heappop(q)
# heapq.heappushpop(q, (dist,i))
ans = [points[ind] for (_, ind) in q]
return ans
LeetCode 347
