Leetcode 973. K Closest Points to Origin

Problem

Leetcode 973 - K Closest Points to Origin

Example:

Input: points = [[1,3],[-2,2]], k = 1
Output: [[-2,2]]
Explanation:
The distance between (1, 3) and the origin is sqrt(10).
The distance between (-2, 2) and the origin is sqrt(8).
Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.
We only want the closest k = 1 points from the origin, so the answer is just [[-2,2]].

Input: points = [[3,3],[5,-1],[-2,4]], k = 2
Output: [[3,3],[-2,4]]
Explanation: The answer [[-2,4],[3,3]] would also be accepted.

Approach

We can use Heap queue to solve this problem. Since heap orders the element by max, when we pop, it pops the minimum element in the heap.

Using this information, we can pop $k$ elements into result.

Here is the Python code for the solution:

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        maxHeap = []
        heapq.heapify(maxHeap)

        for point in points:
            dist = sqrt(point[0] ** 2 + point[1] ** 2):

            heapq.heappush(maxHeap, (dist, point))
        
        res = []
        for i in range(k):
            res.append(heapq.heappop(maxHeap)[1])

        return res    

Time Complexity and Space Complexity

Time Complexity: $O(k * log n)$

Space Complexity: $O(n)$