How do you find the k closest points to the origin?

Q: How do you find the k closest points to the origin?

**Target Audience:** Beginners preparing for coding interviews — you need Python lists, tuples and loops; heaps are explained on the linked page. **Difficulty:** Medium **Language:** Python 3 > **How to read this doc:** every idea is explained in plain words first. When a word appears that an interviewer will expect you to know, it is tagged `📌 Interview term:` with a one-line definition, and every tagged term is collected in the Quick Glossary at the end. Every program on this page was actually run, and the output in the **Verified** section is copied from that run. ## 1. Why This Even Matters — A Story First You open a food delivery app and it shows "the 3 restaurants nearest to you". Your phone is the **origin** of a map, point (0, 0), and every restaurant is a point (x, y) somewhere around it. The app does not need the whole city sorted by distance — it needs only the 3 nearest, and it needs them fast, because thousands of people are asking at the same time. This is the sa

The problem

Question presented to candidate: "You are given a list of points on a plane as [x, y] pairs and a number k. Return the k points closest to the origin (0, 0). Write it in Python and explain the complexity. Any order is fine, but tell me how you would make it deterministic."

What a strong answer should cover:

Compare squared distances x² + y²: same order as the real distance, exact integers, no sqrt.
A max-heap of size k (the root is the farthest kept point): O(n log k) time, O(k) space, one pass.
Quickselect on the squared distance: average O(n), worst O(n²), reorders the list; sorting is the O(n log n) baseline.
Ties: a composite key (distance, x, y) makes the output deterministic.
Python specifics: heapq is a min-heap, so push negated keys (-d, -x, -y) for a max-heap; heapq.nsmallest(k, points, key=...) is the one-liner; Python integers never overflow, so large coordinates are safe; avoid math.sqrt/math.dist in the comparison.

Clarifying questions expected:

How large can the coordinates be, and how should ties be ordered?
Is k small compared with n, and may I reorder the input?

Code / implementation expected: Yes — a size-k heap with heapq (negated keys) in Python, plus the idea of quickselect.

heap
geometry

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Beginners preparing for coding interviews — you need Python lists, tuples and loops; heaps are explained on the linked page.
Difficulty: Medium
Language: Python 3

How to read this doc: every idea is explained in plain words first. When a word appears that an interviewer will expect you to know, it is tagged 📌 Interview term: with a one-line definition, and every tagged term is collected in the Quick Glossary at the end. Every program on this page was actually run, and the output in the Verified section is copied from that run.

1. Why This Even Matters — A Story First

You open a food delivery app and it shows "the 3 restaurants nearest to you". Your phone is the origin of a map, point (0, 0), and every restaurant is a point (x, y) somewhere around it. The app does not need the whole city sorted by distance — it needs only the 3 neare

The solution is hidden so you can try first

9 min read · 11 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonK closest points with a size-k max-heap on squared distance

Practice

PythonSorting vs heap vs quickselect on 50,000 points, and 64-bit squared distances