K Closest Points to Origin
Asked at Airbnb
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| Airbnb | Medium | View all Airbnb questions → |
How to Think About It
Compare squared distances x² + y² — taking square roots is unnecessary and introduces floating-point noise.
Sorting all points by distance is O(n log n) and perfectly acceptable as a first answer.
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.
Quickselect partitions around a pivot distance until the first k positions hold the closest points: O(n) average, O(n²) worst case.
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).
What Trips People Up in Real Interviews
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).
Solution Code
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]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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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)`.