K Closest Points to Origin
On this page
Problem statement
Given a list of points
[x, y]on a plane and an integerk, return thekpoints 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

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
- What if two points tie for the k-th place? (Here: assume the answer is unique; otherwise any of the tied points is fine.)
- Does the output need to be sorted by distance? (Here: no.)
- Is
ksmall compared withn? That decides heap vs sort. - Do all points fit in memory, or do they arrive as a stream? A stream rules out sorting and quickselect.
- Distance to the origin or to some query point? The code is the same with
(x − qx)² + (y − qy)².
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.