K Closest Points to Origin

Free with account Updated Nov 19, 2026 · 6 min read
On this page

    Problem statement

    Given a list of points [x, y] on a plane and an integer k, return the k points closest to the origin (0, 0). Distance is ordinary straight-line (Euclidean) distance. The answer may be in any order, and you may assume it is unique (no tie at the k-th place), or ask what to do with ties.

    You'll often get it in product clothing: "return the k nearest restaurants to the user", "the k drivers closest to a pickup point". The core is the same top-k selection. Original problem: LeetCode 973.

    Example

    Squared distances are 25, 5, 26, 2 and 18, so the two closest points are (1, 1) and (−2, 1).
    Squared distances are 25, 5, 26, 2 and 18, so the two closest points are (1, 1) and (−2, 1).
    Input:  points = [[3,4], [-2,1], [5,-1], [1,1], [-3,-3]], k = 2
    Output: [[1,1], [-2,1]]        # any order
    Input:  points = [[0,7]], k = 1
    Output: [[0,7]]

    Constraints (assumed)

    • 1 ≤ k ≤ n ≤ 10⁴ (or a stream of unknown length in the follow-up).
    • −10⁴ ≤ x, y ≤ 10⁴, so x² + y² fits in 32 bits (just under 2³¹ at the limits; use 64-bit to be safe).

    What this question tests

    • Recognising a top-k problem and picking between sort, heap and quickselect.
    • Knowing which heap to use: to keep the k smallest, you need a max-heap of size k.
    • Avoiding needless work and error: compare squared distances, no square roots.

    Questions to ask first

    1. What if two points tie for the k-th place? (Here: assume the answer is unique; otherwise any of the tied points is fine.)
    2. Does the output need to be sorted by distance? (Here: no.)
    3. Is k small compared with n? That decides heap vs sort.
    4. Do all points fit in memory, or do they arrive as a stream? A stream rules out sorting and quickselect.
    5. Distance to the origin or to some query point? The code is the same with (x − qx)² + (y − qy)².