973. K Closest Points to Origin

Medium

Problem:

When there is a list of points on a plane, print the list of points that are closest to the origin (0,0) in order k times. The distance between two points on the plane is determined using the Euclidean distance.

Example 1:

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]].

Example 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.

https://leetcode.com/problems/k-closest-points-to-origin/

Solution:

From the word 'K times extraction', we can immediately think of a priority queue. We can calculate the Euclidean distance and print it K times using a priority queue.

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        heap = []
        for (x, y) in points:
            dist = x ** 2 + y ** 2
            heapq.heappush(heap, (dist, x, y))
        result = []
        for _ in range(k):
            (dist, x, y) = heapq.heappop(heap)
            result.append((x, y))
            print(result)
        return result

for (x, y) in points

If points is a list of lists (or tuples) where each inner list (or tuple) consists of two elements, you can unpack these values directly in a for loop using the syntax for (x, y) in points:.

Example:

points = [[1,2], [3,4], [5,6]]
for (x, y) in points:
    print(x, y)

This will print:

1 2
3 4
5 6

heapq.heappush(heap, (dist, x, y))

heapq is a Python standard library that provides functions for implementing heaps based on regular lists. The heappush() method pushes a value onto the heap while maintaining the heap invariant (the smallest value is kept at the first position for a min-heap).

heapq.heappush(heap, (dist, x, y)) means you are pushing a tuple (dist, x, y) onto the heap. Tuples in Python are compared lexicographically, so when comparing two tuples, the first item is compared, then the second, and so on. This means, the heap will be primarily organized by the dist value (the distance). Thus, the smallest distance will always be on the top of the heap (i.e., the element at the 0th index).