Return the k points closest to the origin. Any order is fine.
points = [[1,3],[-2,2]], k = 1 → [[-2,2]]
The distance from a point (x, y) to the origin (0, 0) is \sqrt{x^2 + y^2}, read "the square root of x squared plus y squared". This comes from Pythagoras' theorem: the point, the origin and the spot (x, 0) form a right-angled triangle whose two short sides are x and y long.
This is "keep the k best items" again, like 4.17.1, except that "best" now means smallest distance, and the distance must be worked out from two numbers.
Do not take the square root. Distance is \sqrt{x^2 + y^2}, but you are only comparing distances, and the square root is monotonic — it preserves order. So compare x^2 + y^2 directly. That avoids a floating-point operation per point and, more importantly, avoids floating-point rounding making two genuinely different distances compare equal.
Comparing squared distances instead of distances is a habit worth having, and it appears anywhere geometry meets sorting.
Think of it like comparing the area of two square fields to see which is larger. If one has an area of 16 and another has an area of 25, you don't need to calculate their exact side lengths (4 and 5) to know the second field is bigger. Skipping the square root saves calculating the side length!
Then: a size-k heap. You want the k smallest distances, so the item you evict is the largest of the ones you are keeping — which means a max-heap.
Note the flip from 4.17.1, where you wanted the k largest and used a min-heap. The rule is the same in both:
The root must be the item you are about to throw away.
import heapqclass Solution: def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]: heap = [] # (1) max-heap via negation for x, y in points: # (2) d = x * x + y * y # (3) no square root heapq.heappush(heap, (-d, x, y)) # (4) if len(heap) > k: # (5) heapq.heappop(heap) # drop the farthest return [[x, y] for _, x, y in heap] # (6)
ts
function kClosest(points: number[][], k: number): number[][] { // TypeScript has no built-in heap. MaxHeap is the heap from 4.16, here // ordered by squared distance, so pop() removes the farthest point. const heap = new MaxHeap<number[]>((p) => p[0] * p[0] + p[1] * p[1]); // (1) for (const p of points) { // (2) heap.push(p); // (4) if (heap.size > k) heap.pop(); // (5) } return heap.toArray(); // (6)}
(1) An empty heap. Python's heapq keeps the smallest item at the front. We want the farthest of the kept points at the front, because that is the one a closer point should replace. So we store each distance as a negative number. The farthest point has the most negative entry, so it sits at the front.
(2) Visit every point once.
(3) The squared distance. We skip the square root. Square root keeps order: if one squared distance is bigger, so is the real distance. So comparing squared distances gives the same answer. It also avoids decimals, which can round two different distances to look equal.
(4) Push the point, as a group of three: the negated distance first, so the heap orders by distance, then x and y.
(5) Too many points? Remove the front, which is the farthest of the k + 1. It can never be among the k closest, because k closer points are already known.
(6) What is left are the k closest points. We drop the stored distance and return [x, y] pairs.
Take points = [[3, 3], [5, -1], [-2, 4]] and k = 2. Squared distances: 18, 26 and 20.
Point
Squared distance
Heap after push (distances)
Too many?
Heap after
[3, 3]
18
no
[5, −1]
26
no
[−2, 4]
20
yes, remove the farthest, 26
The answer is [[3, 3], [-2, 4]].
Negating the distance turns Python's min-heap into a max-heap, so the root is the farthest of the k kept so far — exactly the one a closer point should replace.
Time Complexity: We iterate through all n points. For each point, pushing to a heap of size k takes O(\log k) time. Popping also takes O(\log k) time. So n points \times O(\log k) operations gives O(n \log k). The squared distance calculation is just O(1).
Space Complexity: We maintain a heap of at most k elements, so it uses O(k) extra memory.
Say this first. It is correct and it establishes the squared-distance point immediately.
Size-k heap — O(n \log k), and it works on a stream, since it never needs all the points at once.
Quickselect — O(n) on average. Partition around a pivot as in quicksort, but recurse into only the side containing the k-th position. After partitioning, the first k elements are the k closest, in no particular order — which is all the problem asks for.
Quickselect's worst case is O(n^2) if pivots are chosen badly, fixed in practice by choosing a random pivot. It also reorders the input.
time
space
works on a stream
sort
O(n \log n)
O(n)
no
size-k heap
O(n \log k)
O(k)
yes
quickselect
O(n) average
O(1)
no
The interview answer is to name all three and the condition that picks each. If they push for the best asymptotic time, quickselect. If they mention a stream or limited memory, the heap.
def kClosest(self, points, k): def dist(p): return p[0]**2 + p[1]**2 def partition(lo, hi) -> int: pivot = dist(points[hi]) store = lo for i in range(lo, hi): if dist(points[i]) < pivot: points[store], points[i] = points[i], points[store] store += 1 points[store], points[hi] = points[hi], points[store] return store lo, hi = 0, len(points) - 1 while lo < hi: p = partition(lo, hi) if p == k: break if p < k: lo = p + 1 else: hi = p - 1 return points[:k]
Why it is O(n) on average: the first partition costs n, the second costs about n/2, then n/4, and so on. That sum is bounded by 2n. Contrast quicksort, which recurses into both halves and pays O(n) per level across \log n levels.
Randomising the pivot before partitioning is what keeps the average case honest on sorted or adversarial input.
Kth Largest Element in an Array — the same three solutions on plain numbers. 4.17.4.
Top K Frequent Elements — same again, over counts, with a bucket-sort option because frequencies are bounded. 4.4.5.
Nearest neighbour search at scale — a k-d tree or a locality-sensitive hash, because a linear scan over billions of points is too slow no matter which selection method follows it.
"Why no square root?" It is monotonic, so it does not change the ordering, and skipping it avoids floating-point error and work.
"Max-heap or min-heap?" Max-heap for the k smallest — the root is what you evict.
"Can you do better than O(n \log k)?" Quickselect, O(n) average, and say why: the partition sizes halve, summing to 2n.
"What if the points arrive as a stream?" Only the heap survives; quickselect needs the whole array.
"What if k is 1?" A single linear scan for the minimum. The general machinery collapses to something much simpler.
One thing to volunteer: state the squared-distance point before writing anything. It is a small thing that immediately signals you have thought about the geometry rather than copied a template.