K closest points to origin: heap, sort and quickselect

In this article

1. Before you start
2. Why interviewers ask this
3. K closest points from first principles
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

This page is one step of the coding interview learning path.

Why interviewers ask this

The problem is a compact test of one habit: do you sort everything when you only need a few answers? Interviewers use it to see whether you notice that selecting k items is cheaper than ordering all n, and whether you can say what each alternative costs. It is a staple of the coding round of an interview loop.

A weak answer sorts the points by distance and slices the first k, which is correct but spends O(n log n) time. A strong answer states that brute force first, then names the heap that keeps only k points, then mentions quickselect, and finishes by saying when each one wins. The problem is also the shape behind real work such as nearest-neighbour search in embedding and vector search and the neighbour step of k-nearest-neighbours classifiers.

K closest points from first principles

K closest points to origin

K closest points to origin is a selection problem that returns the k points of a list with the smallest straight-line distance to the point (0, 0), in any order.

Max-heap

A max-heap is a tree stored in an array that keeps its largest item at the root, so the farthest of the points it holds is always one read away.

Quickselect

Quickselect is a selection algorithm that partitions a list around a random pivot and recurses into only the side that holds the k-th item, so it finds the k smallest items in linear time on average.

In plain words

Picture a shortlist with room for k names. You walk down a long list of candidates. While the shortlist has space, you add everyone. After that, each newcomer is compared with the worst name on the list. A better newcomer replaces the worst name. A weaker one is ignored. At the end the shortlist holds the best k. The analogy breaks in one place: a heap does not keep the shortlist sorted. It keeps only the worst name in easy reach, which is all the comparison needs.

In one precise sentence: keep a max-heap of size k ordered by distance, replace its root whenever a new point is closer than the root, and return the heap's contents. The constraints on the common version of the problem are 1 <= k <= points.length <= 1000 and coordinates between -100 and 100, and the answer may be in any order (NeetCode problem page, as of October 2026).

Big-O and log k in plain words

Two Big-O terms appear below. Big-O counts how the number of steps grows as the input grows. A logarithm, written log, counts how many times you can halve a number before reaching 1: 1,000 halves to 1 in about 10 steps, so log of 1,000 is about 10. O(n log k) therefore means "n points, each costing about log k steps". With n of 1,000 and k of 10, that is about 3,300 steps (1,000 times log of 10, which is about 3.3), against about 10,000 for sorting everything (1,000 times log of 1,000, about 10).¹ The smaller k is, the bigger the saving.

Step 1: Compare squared distances, never square roots

The distance from the origin to a point (x, y) is the square root of x squared plus y squared, but the square root is never needed. If a is smaller than b, then the square root of a is smaller than the square root of b, so ordering by x² + y² gives exactly the same order as ordering by the true distance.

Skipping it saves work and keeps every value an exact integer. A square root returns a floating-point number, and the rounding can only ever turn two different distances into a tie, never reverse them. That needs a distance beyond about 67 million (2^26), which coordinates of about 47.5 million can already reach: the points (67,108,864, 0) and (67,108,864, 1) have different squared distances but the same floating-point square root.² Under the problem's limit of 100 the root never changes an answer, so it is unnecessary work, not a hidden bug. For the points (1, 3), (-2, 2), (5, 8) and (0, 1), the squared distances are 10, 8, 89 and 1.

Step 2: Fill the heap with the first k points

The first k points go into the heap with no comparison, because there is nothing to beat yet. Python's undefined module implements a min-heap, whose smallest item is always heap[0], so a max-heap is built by storing the negative of each squared distance. Python 3.14 added public max-heap functions such as heappush_max, heapreplace_max and heapify_max (Python docs, as of October 2026); negation works on every version, and an online judge may run an older Python, so this page uses it. The common slip is a plain min-heap of the positive distances, which keeps the k farthest points because its root is the smallest item, not the largest.

With k equal to 2 on the four points above, the heap receives the entries for 10 and 8. Its root, the item you can read in constant time, is the one with squared distance 10, the farthest point kept so far. Input: the first k points. Output: a full heap whose root is the current k-th closest. That root is the number every later point must beat.

Step 3: Beat the root or skip the point

Every later point is compared with the root. If its squared distance is larger than the root's, the point is farther than all k points held, so it is skipped. If it is smaller, the root is removed and the new point is pushed in, which Python does in one call, heapq.heapreplace.

In the example, the point (5, 8) has squared distance 89, which exceeds the root's 10, so it is skipped. The point (0, 1) has squared distance 1, which is smaller than 10, so it replaces the root. Each replacement costs O(log k) time because the heap restores its order by moving one item along a path as tall as the heap. Skipping costs one comparison.

Step 4: Read the answer from the heap

After the last point, the heap holds exactly the k closest points, in no particular order. In the example the heap holds the points with squared distances 8 and 1, which are (-2, 2) and (0, 1). Returning them completes the algorithm, and the problem says any order is acceptable.

Total cost: n comparisons with the root plus at most n replacements of O(log k) each, so O(n log k) time and O(k) extra memory. When k is small next to n, that is close to linear.

1 · Squared distances2 · Fill the heap3 · Beat or skip4 · Read the answerReplay

Step-by-step description

1. Square and add, no square root.
2. The first k points go in; the root is the farthest.
3. A point replaces the root only if it is closer.
4. The heap holds the k closest points.

• The squared distances are 10, 8, 89 and 1.
• The point with squared distance 89 is skipped because it exceeds the root.
• The point (0, 1) has squared distance 1, which is smaller than 10, so it replaces the root.

The whole solution fits in a few lines of Python.

import heapq

def k_closest(points, k):
    heap = []                                   # max-heap via negated squared distance
    for x, y in points:
        item = (-(x * x + y * y), x, y)
        if len(heap) < k:
            heapq.heappush(heap, item)
        elif item > heap[0]:                    # closer than the current k-th closest
            heapq.heapreplace(heap, item)
    return [[x, y] for _, x, y in heap]

The code stores negative distances because heapq gives the smallest item first; the largest squared distance is then the smallest negative number, which sits at the root. The comparison item > heap[0] means "closer than the root". A tuple compares by its first element, then by the coordinates, which only matters for ties.

Worked example

The sorting, heap and quickselect solutions were run on 1,000 seeded random points with coordinates from -100 to 100 and k equal to 10, and they returned the same set of distances.¹ Every comparison between two squared distances was counted the same way, including those made inside sorted and heapq: a full sort used 8,657, the size-k heap used 1,231 (990 checks against its root, 241 inside heapq, and 54 root replacements), and quickselect used 1,900.¹ Heapify-and-pop, the valid alternative described under Common mistakes, used 1,731.¹ The solutions also agreed on 300 smaller random inputs.¹

These counts are one seeded run, not a benchmark: a heap does one check per point plus a few cheap replacements, while a sort orders everything. The heap's count would be higher if the input were sorted from farthest to nearest, because then every point beats the root.

Text description of the diagram

• A full sort used 8,657 comparisons.
• The heap of size k used 1,231 in total (990 root checks, 241 inside heapq) and quickselect used 1,900.

Trade-offs and edge cases

Each method wins a different row, so the right answer depends on what the interviewer adds to the problem.

Sorting takes O(n log n) time and is the simplest to write. Python sorts with Timsort, which the Python sorting guide says exploits order already in the data, and sorted(points, key=...) is one line. It holds all n points.

The heap runs in O(n log k) time and O(k) memory, and it works on a stream of points that never fits in memory, because it needs only one pass. The heapq documentation (Python docs, as of October 2026) says nsmallest and nlargest perform best when the number of items requested is small, and that sorted() is more efficient when that number is large; that is the same reason a heap of size k loses its edge as k nears n.

Quickselect runs in O(n) time on average, but its worst case is O(n²) when pivots are chosen badly, and a random pivot makes that extremely unlikely (Quickselect, Wikipedia, as of October 2026, which credits Hoare, 1961). It rearranges the list in place, so it needs the whole list in memory.

Text description of the diagram

• Sorting takes O(n log n) time and is the simplest to write.
• The heap takes O(n log k) time and O(k) memory and works on a stream.
• Quickselect takes O(n) time on average but O(n squared) in the worst case.

Edge cases: when k equals n, return everything without any heap; the usual statement states the answer is unique, so a tie at the k-th place does not occur in its tests, and if an interviewer allows ties, any of the tied points is a valid answer, so say so; and for very large coordinates, compare squared distances as integers, which Python handles without overflow, while fixed-width languages need a wider integer type (and beyond a distance of about 67 million, a floating-point square root can create false ties).

The same selection idea appears in the machine learning coding round. Real systems that search millions of vectors use specialised indexes, covered in embedding and vector search and the system design guide.

How to answer it in an interview

The spoken structure: say the brute force and its cost, say the heap and why squared distance, then name quickselect and the trade-off.

Common mistakes

• "I take the square root of every distance." (wrong) It adds work and changes no ordering under the problem's limits. (right) "I compare squared distances; the order is identical."
• "I heappush all n points and pop k." (wrong) That builds a heap of n items, which costs O(n log n) time and O(n) memory. (right) "I keep a max-heap of size k so the farthest kept point is at the root." Heapify-and-pop, which builds the heap in O(n) and pops k times for O(n + k log n), is a valid option when everything fits in memory; its price is O(n) memory and no streaming (1,731 comparisons here against 1,231 for the size-k heap).
• "I push every point and then trim the heap." (wrong) The heap grows to n and the O(log k) bound is lost. (right) "I replace the root only when a point is closer, so the heap never exceeds k."
• "Quickselect is always linear." (wrong) A bad pivot sequence makes it quadratic. (right) "It is linear on average with a random pivot; I would say so and name the worst case."

Follow-up questions

Kth largest element: heap or quickselect?

Use a min-heap of size k for the k-th largest element on a stream or when k is small: its root after one pass is the answer, in O(n log k) time. Use quickselect when the list is in memory and you want linear average time; both answer the same question the closest-points problem asks.

Given m arrays of size n, how do you find the Kth largest element?

If the arrays are unsorted, push every element through one min-heap of size k, which costs O(m n log k) time; its root at the end is the answer. If each array is already sorted, put the largest element of each array in a max-heap (m entries), pop k times and after each pop push the next element of the same array: O(m + k log m) time.

Find K Pairs with Smallest Sums: how does the heap help?

Given two sorted arrays, the smallest pair sum is the first element of each. Put that pair in a min-heap, pop the smallest, and push its two neighbours (next element of either array) that are not yet seen. After k pops you have the k smallest sums, in O(k log k) time, without forming all pairs.

Top k frequent elements: does the same heap work?

Yes. Count each value with a dictionary in O(n), then keep a min-heap of size k keyed by count: replace the root when a value's count is larger. That is O(n log k) time, and the heap now holds the k most frequent values.

What if the points arrive as a stream?

Keep the size-k max-heap and update it as each point arrives; at any moment it holds the k closest points seen so far. Sorting and quickselect both need the whole list first, so only the heap works here.

What changes if k is close to n?

A heap of size k is then almost as large as the input, so its O(n log k) cost approaches a full sort. Select the n minus k farthest points instead, or just sort, because the savings disappear.

Sources

1. heapq: Heap queue algorithm — Python Software Foundation documentation (date = read date), 24 Oct 2026
2. Sorting Techniques (Sorting HOW TO) — Python Software Foundation documentation (date = read date), 24 Oct 2026
3. K Closest Points to Origin (problem statement and constraints) — NeetCode (date = read date), 24 Oct 2026
4. Quickselect — Wikipedia, pointer to Hoare (1961), Algorithm 65: Find (date = read date), 24 Oct 2026