MediumArrayMathDivide and ConquerGeometrySortingHeap (Priority Queue)Quickselect

K Closest Points to Origin

Practise with tests LeetCode

1 approach, code in every language

You are given an array `points` where `points[i] = [xi, yi]` is a point on the 2D plane, along with an integer `k`.

Return the `k` points that are closest to the origin `(0, 0)`, measured by Euclidean distance sqrt(x^2 + y^2).

The answer may be returned in any order, and it is guaranteed to be unique except for that ordering.

Example 1

Input: points = [[1,3],[-2,2]], k = 1

Output: [[-2,2]]

The distance of [1,3] is sqrt(10) and of [-2,2] is sqrt(8). Since sqrt(8) < sqrt(10), the single closest point is [-2,2].

Example 2

Input: points = [[3,3],[5,-1],[-2,4]], k = 2

Output: [[3,3],[-2,4]]

The squared distances are 18, 26 and 20; the two smallest belong to [3,3] and [-2,4]. Any order of these two is accepted.

Constraints

1 <= k <= points.length <= 10^4
-10^4 <= xi, yi <= 10^4

Size-k max-heap on squared distance

Keep the k nearest points in a max-heap keyed on squared distance, evicting the farthest whenever the heap overflows.

Loading animation…

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

1Create a max-heap ordered by squared distance x^2 + y^2 so the farthest candidate is at the root.
2For each point, compute its squared distance and push the point onto the heap.
3If the heap size exceeds k, pop the root to remove the point that is currently farthest from the origin.
4Using squared distance avoids computing square roots and keeps all arithmetic in integers.
5After every point is processed, the heap holds the k points nearest the origin.
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]

Time

O(n log k)

Space

O(k)

Each of the n points triggers a push and possibly a pop, each O(log k). A Quickselect on squared distances runs in O(n) average time.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Priority Queues

After the pattern

Now solve one you haven't seen.

Nearest Survey Stakes is our own problem on the technique behind K Closest Points to Origin: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free