Skip to content
DSAPrep

    ↑↓ to move · Enter to open · Esc to close

    MediumHeap / Priority Queue

    K Closest Points to Origin

    Given an array of points where points[i] = [x_i, y_i] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).

    The distance between two points on the X-Y plane is the Euclidean distance (i.e., √((x1 - x2)^2 + (y1 - y2)^2)).

    You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in).

    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, and k = 1 so it is the only answer.

    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.

    Constraints

    • 1 <= k <= points.length <= 10^4
    • -10^4 <= x_i, y_i <= 10^4
    View original on LeetCode ↗

    There’s no need to compare every point to every other point, and no need for an exact square root either — since distances are only ever compared to each other, the squared distance x² + y² preserves order and avoids floating point. The real question is how to get the k smallest distances without fully sorting: keep a max-heap of size k, so its root is always the farthest point among the current top-k closest — the moment a new point beats it, swap it in.

    Sort by Distance

    Time O(n log n)Space O(n)

    Compute every point’s squared distance, sort by it, and take the first k.

    class Solution:
        def kClosest(self, points: list[list[int]], k: int) -> list[list[int]]:
            points.sort(key=lambda p: p[0] ** 2 + p[1] ** 2)
            return points[:k]

    This is correct and often accepted since n <= 10^4, but it does more work than necessary: it fully orders all n points when we only need the smallest k separated from the rest, not globally sorted.

    Max-Heap of Size k

    OptimalTime O(n log k)Space O(k)

    Walk the points once. Push each (-distance, x, y) onto a max-heap (negated for Python’s min-heap) capped at size k. Whenever the heap grows past k, pop the farthest point — it can no longer be among the k closest once k better candidates exist.

    import heapq
    

    class Solution:
        def kClosest(self, 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]

    Watch the heap root: it is always the farthest of the current candidates, and when the heap grows past k that root is exactly what gets popped.

    Points left to right

    (3,3)d=18
    (5,-1)d=26
    (-2,4)d=20

    Max-heap, size 0 / k = 2 (root = farthest)

    empty
    root
    empty
    1
    empty
    2
    1 / 10
    currentseencomparingresultdiscarded

    A size-k max-heap keeps the k closest points seen so far; its root is the farthest. Walk the points left to right and watch the root.

    Correctness: the heap only ever holds k points — the closest k seen so far. Any point evicted was, at the time, the farthest among k+1 candidates, so it can never end up in the final top-k (adding more points only ever introduces more competition, never removes it).

    Complexity: each of the n points does one push and at most one pop on a heap capped at size k, so O(n log k). This beats full sorting whenever k is small relative to n. Space is O(k) for the heap (plus O(n) for the output list).

    More Heap / Priority Queue practice