MediumArrayMathDivide and ConquerGeometrySortingHeapQuickselectUpdated Sep 2026

973. K Closest Points to Origin

Asked at Airbnb

Difficulty

Medium

Time

O(n log k)

Space

O(k)

Pattern

Array

Companies

1

Problem

You are given a list of points on a flat plane. Each point is written as [x, y]. You are also given an integer k.

Return the k points that are closest to the origin (0, 0). Closeness means Euclidean distance: the straight-line distance from the point to the origin. The order of the points you return does not matter.

The answer is guaranteed to be unique, so there is no tie to break — only the ordering inside your answer is free.

Pick the k nearest points

pointspointx²+y²p0p1p2[3,3]18[5,-1]26[-2,4]20k = 2, so keep the rows with the two smallestdistances
Only the distance to the origin matters. Here the two smallest squared distances are 18 and 20.

Constraints

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

Examples

Example 1
Inputpoints = [[1,3],[-2,2]], k = 1
Output[[-2,2]]
WhySquared distances are 1²+3² = 10 and (-2)²+2² = 8. Since 8 < 10, the point (-2,2) is nearer to the origin, and we only need the single closest point.
Example 2
Inputpoints = [[3,3],[5,-1],[-2,4]], k = 2
Output[[3,3],[-2,4]]
WhySquared distances are 18, 26 and 20. The two smallest are 18 and 20, so those two points are the answer. Writing them as [[-2,4],[3,3]] is also accepted.

Asked At

1 companies
CompanyDifficulty
AirbnbMediumView all Airbnb questions →

How to Think About It

1

Compare squared distances x² + y² — taking square roots is unnecessary and introduces floating-point noise.

2

Sorting all points by distance is O(n log n) and perfectly acceptable as a first answer.

3

Heap approach: keep a max-heap of size k keyed by distance. For each point, push it; if the heap grows past k, pop the farthest. Result: the k closest in O(n log k) — good when n is huge or streaming.

4

Quickselect partitions around a pivot distance until the first k positions hold the closest points: O(n) average, O(n²) worst case.

5

Walkthrough: [[3,3],[5,-1],[-2,4]], k = 2. Squared distances 18, 26, 20. Keep 18 and 20 -> [[3,3],[-2,4]].

Optimal Approach

Step 1: Max-heap h (store negated distances in Python).
Step 2: For each point (x, y):
Push (-(x*x + y*y), x, y).
If len(h) > k: pop the farthest.
Step 3: Return the points left in the heap.

Time: O(n log k). Space: O(k).

Max-heap of size k

heap (farthest on top)(18, [3,3])← topPush [3,3] with distance 18 — heap size 1, still underkheap (farthest on top)(26, [5,-1])(18, [3,3])← topPush [5,-1] with distance 26 — heap size 2, stillunder kheap (farthest on top)(20, [-2,4])(18, [3,3])← topPush [-2,4] with distance 20, then pop 26 because theheap grew past kpush (x²+y², x, y)if size > k: pop the maxanswer = what is left
The heap always keeps the k closest points seen so far; the farthest one sits on top and gets removed when a better point arrives.
ComplexityTime O(n log k)Space O(k)Each of the n points is pushed into a heap that never holds more than k items, so every heap operation costs O(log k).

What Trips People Up in Real Interviews

1

Using a min-heap of all n points and popping k times — that is O(n + k log n) with O(n) space; say why the size-k max-heap is better for streams.

2

Computing sqrt. Squared distances preserve order and avoid precision issues.

3

Assuming the output must be sorted. Any order is accepted.

4

Not mentioning quickselect when asked for better than O(n log n).

Solution Code

O(n log k) time
import heapq

def kClosest(points, k):
    h = []
    for x, y in points:
        heapq.heappush(h, (-(x * x + y * y), x, y))
        if len(h) > k:
            heapq.heappop(h)
    return [[x, y] for _, x, y in h]

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the K Closest Points to Origin problem?

K Closest Points to Origin asks for the `k` points nearest to `(0, 0)`, in any order. It is a top-k selection problem, and interviewers usually want to hear the trade-offs between sorting, a size-`k` heap, and quickselect.

How do you solve K Closest Points to Origin?

The optimal approach runs in O(n log k) time and O(k) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask K Closest Points to Origin?

K Closest Points to Origin is asked at Airbnb. It is a medium difficulty problem.

What are common mistakes on K Closest Points to Origin?
  • Using a min-heap of all `n` points and popping `k` times — that is `O(n + k log n)` with `O(n)` space; say why the size-`k` max-heap is better for streams.
  • Computing `sqrt`. Squared distances preserve order and avoid precision issues.
  • Assuming the output must be sorted. Any order is accepted.
  • Not mentioning quickselect when asked for better than `O(n log n)`.