K Closest Points to Origin

Intuition

Comparing Euclidean distances never requires the square root — since sqrt is monotonic, ordering by x^2 + y^2 gives the same result while avoiding floating-point work. To retain the k closest points we use a max-heap keyed on that squared distance so the current farthest of our candidates sits at the root. As we scan the points we push each one and, whenever the heap exceeds size k, pop the root to discard the farthest. What remains after the scan are exactly the k closest points, ready to return in any order.

Algorithm walkthrough

1. 1Create a max-heap ordered by squared distance x^2 + y^2 so the farthest candidate is at the root.
2. 2For each point, compute its squared distance and push the point onto the heap.
3. 3If the heap size exceeds k, pop the root to remove the point that is currently farthest from the origin.
4. 4Using squared distance avoids computing square roots and keeps all arithmetic in integers.
5. 5After every point is processed, the heap holds the k points nearest the origin.
6. 6Collect and return the heap's contents; the order does not matter.

Implementation

import heapq
from typing import List

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        heap = []  # max-heap: store (-dist, x, y)
        for x, y in points:
            dist = x * x + y * y
            heapq.heappush(heap, (-dist, x, y))
            if len(heap) > k:
                heapq.heappop(heap)
        return [[x, y] for _, x, y in heap]