Coding interview problems › Heaps & Top-K

🔺 Heaps & Top-K Medium

K Closest Points to Origin

K Closest Points to Origin: keep a size-k max-heap of squared distances, no square roots needed, O(n log k). Tested Python, pitfalls and a live heap visual.

Also searched as: k nearest points to origin · k closest points using max heap · closest points heap problem

🔺

Try it live Free

Binary Heap & Priority Queue

Watch push bubble a value up and pop remove the root in the heap lab; here the root is the farthest of the k kept points, so each pop discards the worst candidate.

Also useful: Quickselect & the k-th Largest

Open the playground →

The problem

Given a list of points [x, y] on a plane and an integer k, return the k points closest to the origin (0, 0) by straight-line distance, in any order. Assume there is no tie at the k-th place.

Inputpoints = [[1, 3], [-2, 2], [5, -1]], k = 1
Output[[-2, 2]]

Squared distances are 10, 8 and 26.

The key insight

You want the k smallest distances, so keep a heap of size k whose root is the largest distance kept so far: the first one to evict when something closer arrives. Python only has a min-heap, so store negated distances. And compare squared distances; the square root does not change the order.

Brute force first: Sorting all points by distance is O(n log n). It is fine for small inputs but does more work than needed when k is much smaller than n.

Step-by-step approach

  1. For each point, compute d = x*x + y*y.
  2. Push (-d, x, y) onto a heap, so the farthest kept point sits at the root.
  3. If the heap holds more than k points, pop the root, the farthest one.
  4. At the end the heap holds the k closest points; return their coordinates.

Python solution

PYTHON 3tested
import heapq


def k_closest(points, k):
    heap = []                               # max-heap via negated distance
    for x, y in points:
        heapq.heappush(heap, (-(x * x + y * y), x, y))
        if len(heap) > k:
            heapq.heappop(heap)             # evict the farthest kept point
    return [[x, y] for _, x, y in heap]

Complexity

TimeO(n log k)
SpaceO(k)

Each of the n points causes at most one push and one pop on a heap of size k + 1.

Common mistakes

Frequently asked questions

What is the time and space complexity?

O(n log k) time with a size-k heap and O(k) extra space.

Why compare squared distances?

Square root is increasing, so ordering by x² + y² gives exactly the same order as ordering by true distance, using only integer arithmetic.

Is there a faster approach?

Quickselect on the squared distances finds the k closest points in O(n) average time, at the cost of an O(n²) worst case and more code.

Can I use heapq.nsmallest?

Yes: heapq.nsmallest(k, points, key=lambda p: p[0]**2 + p[1]**2) solves it in one line with the same O(n log k) idea.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Heaps & Top-K Binary Heap & Priority Queue lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.