The problem
Given points on a grid and k, return the k points closest to the origin (0, 0), using ordinary straight-line distance.
Input: points = (3,3) (5,−1) (−2,4) (1,−3) (−4,−2), k = 2 Output: [(1,−3), (3,3)]
Picture it
Picture yourself living at the centre of a map and the points are cafés. We want the k nearest. We don’t need real distances, just which is nearer, so we compare x² + y² (no square root). A heap keeps the k best so far: if we find a café nearer than the farthest one we’re keeping, it replaces it.
How to recognise it
- You must return the k best items by some score (here, distance from the origin), not just one.
- The score is cheap to compute for each item, and you only need the k winners, not a full ranking.
- The order of the answer does not matter, which is a hint that sorting everything is more than you need.
- k is often much smaller than n, and the same idea works when the points arrive as a stream or do not fit in memory.
- "Top k by a score" suggests a heap (a tree stored in a list with O(log n) push and pop) that holds k candidates and throws out the worst one when a better one arrives.
Start with brute force
Compute the squared distance of every point, sort all points by it, and take the first k.
def k_closest_brute(points, k):
ordered = sorted(points, key=lambda p: p[0] * p[0] + p[1] * p[1])
return ordered[:k]
Time is O(n log n) for the sort and space is O(n) for the sorted copy. With n up to 10^4 that is only about 10^5 comparisons, so this passes the limits. It is still wasteful: it fully orders 10^4 points to keep, say, 10. If n were 10^7 and k were 10, you would pay for a 10^7-item sort and hold every point in memory.
From brute force to the idea
- Find the waste. The sort ranks points that can never be in the answer, such as the 5,000th closest.
- Skip the square root. Distance order is the same as squared-distance order, so use
x*x + y*y. This keeps everything in exact integers. - Keep a leaderboard of size k. Hold the k closest points seen so far. The one to throw out when a better point arrives is the farthest of them.
- Use a max-heap by distance. Python's
heapqonly has a min-heap, so push(-d, x, y): the most negative entry is the farthest point and sits at the front. - Push, then trim. After each push, if the heap holds more than k entries,
heappopremoves the farthest. What remains at the end is the k closest.
This is the key idea: a max-heap of size k keyed on squared distance, so each point costs O(log k).
The key idea
Compare squared distances; keep a max-heap of size k (or heapify and pop k). O(n log k).
Python solution
def k_closest(points, k):
heap = [] # max-heap of the k closest (negated)
for x, y in points:
d = x * x + y * y
heappush(heap, (-d, x, y))
if len(heap) > k:
heappop(heap) # drop the farthest
return [[x, y] for _, x, y in heap]LeetCode adds the imports for you. To run this on your own machine, put this at the top: from heapq import heappush, heappop
In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force (sort all) | O(n log n) | O(n): the sorted copy |
| Max-heap of size k (shown code) | O(n log k): one push and at most one pop per point, each on a heap of at most k + 1 items | O(k): only the candidates are kept |
Edge cases
- k equals n: nothing is ever popped, so every point is returned.
- Single point at the origin (
[[0, 0]], k = 1): returns[[0, 0]]. - Very large coordinates (
[10000, 10000]): the squared distance is 2 × 10^8, and Python integers do not overflow. In Java or C++, 32-bit ints still hold it, but 10^5 coordinates would needlong. - Ties at the boundary (
[[1, 0], [-1, 0]], k = 1): the code keeps[1, 0], because tuples tie-break onxand the smaller one is popped. The problem promises a unique answer, so this only matters if you reuse the function. - Order of the result: it is heap order, not sorted by distance. The problem allows any order.
- k = 0: returns an empty list.
- Imports:
heappushandheappopcome fromheapqand are not in the snippet.
Common mistakes
- Pushing the positive distance, which makes the heap keep the k farthest points. On
[[3, 3], [5, -1], [-2, 4]]with k = 2 it returns the points at squared distances 20 and 26, instead of 18 and 20. - Taking
sqrtand comparing floats, which adds cost and a risk of rounding for no benefit. - Storing only the distance in the heap, so you cannot say which point it belonged to.
- Building a min-heap of all n points and popping k times. It is correct, but O(n + k log n) time and O(n) space.
Return the k points farthest from the origin. Describe your approach, then write it if you like.
Compare with our answer
Flip which end you throw away. Keep the k farthest so far; the one to evict is the nearest of them, so a plain min-heap on squared distance does the job with no negation.
from heapq import heappush, heappop
def k_farthest(points, k):
heap = [] # min-heap of the k farthest
for x, y in points:
heappush(heap, (x * x + y * y, x, y))
if len(heap) > k:
heappop(heap) # drop the nearest
return [[x, y] for _, x, y in heap]
With [[3, 3], [5, -1], [-2, 4]] and k = 2 it returns the points at squared distances 20 and 26. Time O(n log k), space O(k).
A strong answer mentions: a min-heap of size k this time, that the nearest candidate is evicted, and that the cost is still O(n log k).
1. A map app has 10 million places and must show the 20 closest to the user at every refresh. Which approach fits best?
A size-20 max-heap costs O(n log 20) and stores only 20 places. Sorting or heapifying everything costs more memory and time, and the square root adds nothing because squared distance gives the same order.
2. What is the time complexity of the shown solution?
Every one of the n points is pushed, and each push or pop on a heap of about k items costs O(log k). The loop does not skip points, and the heap is never fully sorted.
3. A learner pushes (d, x, y) without the minus sign. Which test still passes?
Without the minus sign the heap pops the nearest point, so it keeps the k farthest. When k equals n nothing is popped, so the test still passes. The first test returns distances 20 and 26 instead of 18 and 20, the second keeps 10 instead of 8, and the third keeps 8 instead of 1.
Score 60% or more and the lesson is marked complete.