The k depots nearest the warehouse

Heaps and priority queues Mid-level Python 3.13+ Reviewed 1 Nov 2026 By Best Latest Apps

Predict the output

What does this print?

Python 3.13

import heapq
pts = [[3, 4], [1, -1], [0, 2], [-2, 0]]
print(heapq.nsmallest(2, pts, key=lambda p: (p[0] ** 2 + p[1] ** 2, p)))

Options[[1, -1], [-2, 0]][[1, -1], [0, 2]][[0, 2], [1, -1]]

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A [[1, -1], [-2, 0]]

Right: squared distances are 25, 2, 4 and 4; the tie between 4s goes to the smaller x.

A key that includes the point itself turns ties into a fixed order, so every run gives the same answer.

Why not the others?

B [[1, -1], [0, 2]]. [-2, 0] and [0, 2] tie on distance 4, and -2 < 0.
C [[0, 2], [1, -1]]. Results come nearest first.

30-second answer

Squared distance x² + y² orders points the same way as real distance, with no square roots. Keep a max-heap of size k on (distance, x, y) by pushing negated keys; pop when it grows past k. Then sort the k survivors. O(n log k) time, O(k) memory.

Practise saying it · 45 s. No recording, just a timer

Explain finding the k nearest points.

Say your answer out loud, then check which of these points you covered:

Squared distance
Max-heap of size k
O(n log k)

Deep dive

Comparing squared distances avoids floating point entirely.

heapq.nsmallest(k, pts, key=...) is a fine one-line answer if allowed.

Fixing a tie rule makes the output deterministic, which also helps testing.

Python solution Ran on Python 3.13.5 · mypy --strict

Python 3.13

from heapq import heappop, heappush


def nearest(depots: list[list[int]], k: int) -> list[list[int]]:
    worst_first: list[tuple[int, int, int]] = []  # negated keys
    for x, y in depots:
        heappush(worst_first, (-(x * x + y * y), -x, -y))
        if len(worst_first) > k:
            heappop(worst_first)  # the farthest of k + 1 goes
    best = sorted((-d, -x, -y) for d, x, y in worst_first)
    return [[x, y] for _, x, y in best]

Common mistakes

Taking square roots and comparing floats.
Using a min-heap of all n points when k is small.

Senior take & follow-ups

Mention dropping the square root early; it is a small, practical point.

Follow-up questions

Think of your answer first, then open the hint.

What if points arrive as a stream?
Show hint
Keep the same size-k max-heap; the answer is always the heap's contents.
How would you do it in average O(n)?
Show hint
Quickselect on squared distance, then sort the first k.

What each operation costs: Min Heap · Max Heap · Heap Operations · Priority Queue

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.