K Closest Points to Origin

PracticeNeetCode ↗LeetCode ↗

Given a list of points on the X-Y plane and an integer k, return the k points closest to the origin (0, 0), in any order.

Example

Key Pointers

• Comparing distances only needs the squared distance — taking a square root doesn't change the ordering and just wastes time.
• A max-heap capped at size k avoids sorting the entire list: it always evicts the farthest of the current top-k candidates.
• Python's heapq is min-only, so negate the distance to make the heap behave like a max-heap.

Step-by-Step Analysis

1. Create an empty heap.
2. For each point, compute dist = x*x + y*y and push (-dist, x, y).
3. If the heap grows past size k, pop the top — the currently farthest of the kept points.
4. Once every point is processed, the heap holds exactly the k closest — return them.

Complexity

Time: O(n log k) — Space: O(k)

Code

import heapq

def kClosest(points: list[list[int]], k: int) -> list[list[int]]:
    heap = []
    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]

Code Explanation

How the solution above works, piece by piece.

1. dist = x*x + y*y: the squared distance. The square root isn't needed because it doesn't change which point is closer.
2. Push (-dist, x, y): negating makes Python's min-heap act as a max-heap, so the farthest point is on top.
3. When the heap holds more than k points, pop the top, the farthest one.
4. At the end the heap holds the k closest points (in no particular order, which the problem allows).
5. O(n log k) time, O(k) space.

Visual Walkthrough

Running it on points = [[1, 3], [-2, 2]], k = 1:

Video Explanation

NeetCode — Heap / Priority Queue, LeetCode 973