LeetCode 973 · Heap / Priority Queue

K Closest Points to Origin, explained with a picture

The k cafés nearest your home.

MediumHeap / Priority Queue
▶ Watch it step by step

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

  1. Find the waste. The sort ranks points that can never be in the answer, such as the 5,000th closest.
  2. 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.
  3. 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.
  4. Use a max-heap by distance. Python's heapq only has a min-heap, so push (-d, x, y): the most negative entry is the farthest point and sits at the front.
  5. Push, then trim. After each push, if the heap holds more than k entries, heappop removes 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

ApproachTimeSpace
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 itemsO(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 need long.
  • Ties at the boundary ([[1, 0], [-1, 0]], k = 1): the code keeps [1, 0], because tuples tie-break on x and 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: heappush and heappop come from heapq and 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 sqrt and 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.
Your turn: k farthest points

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).

Check what stuck

1. A map app has 10 million places and must show the 20 closest to the user at every refresh. Which approach fits best?

2. What is the time complexity of the shown solution?

3. A learner pushes (d, x, y) without the minus sign. Which test still passes?

Score 60% or more and the lesson is marked complete.