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

Tracing points = [[3,3],[5,-1],[-2,4]], k = 2 (squared distances: 18, 26, 20):

(3,3):18
0
1 / 4
comparingresultcurrent

Push (3,3), dist=18. Heap size 1 <= k, keep it.

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