973. K Closest Points to Origin

973

MediumHeap and Priority QueueMax-heap of size k (top-k selection)Bounded max-heap for k nearest

K Closest Points to Origin

Given an array points where points[i] = [xi, yi] represents a point on the plane, and an integer k, return the k points closest to the origin (0, 0) measured by Euclidean distance. The answer may be returned in any order and is guaranteed to be unique.

Open official problem prompt ↗

In plain English

Return the k points with the smallest distances to the origin, ignoring their relative order.

Picture it like this

Keeping a shortlist of the k nearest friends on a map: whenever you spot someone closer than your current farthest shortlisted friend, drop that farthest one and add the newcomer.

Example

Input: points = [[1, 3], [-2, 2]], k = 1
Output: [[-2, 2]]
Why: Squared distances are 1+9 = 10 and 4+4 = 8; [-2,2] is closer, so it is the single closest point.

Constraints

1 <= k <= points.length <= 10^4-10^4 <= xi, yi <= 10^4

Pattern lesson

See the pattern, then code

Bounded max-heap for k nearest

↗

Heap and Priority Queue

Top k, kth value, repeated minimum extraction, scheduling, or merging sorted streams.. Rank points by squared distance (no square root needed since it preserves order). Keep a max-heap of the k closest so far; if a new point is closer than the current farthest in the heap, swap it in. The heap never grows beyond k.

New words, made simpleKnow these before the algorithm

Squared distance: x^2 + y^2, used instead of sqrt(x^2+y^2) because it orders points identically and avoids floating point.
Top-k / selection: Finding the k best by some key without fully sorting the rest.
heapreplace: A single O(log k) operation that pops the root and pushes a new element, cheaper than a separate pop then push.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Sort all points by distance

Correct but does more work than necessary when k is much smaller than n.

Sort the whole array by squared distance and take the first k.

Time O(n log n)Space O(n)

Best choiceSize-k max-heap

Scales better for small k and uses only O(k) memory.

Maintain a heap of the k closest seen; replace the farthest whenever a closer point appears.

Time O(n log k)Space O(k)

Quickselect

Fastest on average but worst-case O(n^2) and harder to get right under pressure.

Partition around a pivot distance to isolate the k smallest.

Time O(n) averageSpace O(1)

The rule we keep true

Invariant

After processing each point, the heap holds the k closest points among all seen so far, with the farthest of them at the root.

Why this is correct

Reasoning

A max-heap of size k exposes its worst (farthest) member at the root. A new point can only belong in the answer if it is closer than that worst member, and replacing the root with it keeps the heap holding the k closest. Since squared distance is monotonic in true distance, using it never changes which points are selected.

The algorithm in three movesSay these aloud before coding

1Compute squared distance x*x + y*y for each point

k=1, heap holds 1 farthest-at-root

2Push into a max-heap while it holds fewer than k points

see [1,3] d=10 -> heap=[(-10,1,3)]

3Otherwise, if the point beats the heap's farthest, replace the root

see [-2,2] d=8: 8<10 -> replace -> [(-8,-2,2)]

4Return the points remaining in the heap

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

[1,3]=100

[-2,2]=81

1 · Readdist = 1+9 = 10

2 · AskHeap has < k?

3 · Update stateheap = [(-10, 1, 3)]

4 · Resultpushed (size now 1 == k)

Key takeaway

Squared distances drive a size-1 max-heap; the closer point [-2,2] replaces [1,3].

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 7-8Distance key
Use squared distance to rank points; taking the square root is unnecessary and only adds floating-point cost.
2
Lines 9-10Fill to k
While fewer than k points are held, push each with negated distance so the heap acts as a max-heap.
3
Lines 11-12Replace the farthest
Once full, a point closer than the root (heap[0][0] holds the negated max distance) evicts the current farthest via heapreplace.
4
Lines 13Extract the answer
Return the [x, y] pairs left in the heap; order does not matter per the problem.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

k equals the number of points (return all)
k == 1 (nearest single point)
points with equal distances (any valid tie-break is accepted since the answer is unique by the guarantee)
points at the origin with distance 0

Common beginner mistakes

Comparing raw distances with sqrt and hitting floating-point ties or slowdowns
Building a max-heap of all n points instead of capping at k, losing the memory advantage
Sign errors when negating distances for Python's min-heap
Assuming a required output order — any order is fine

Check your understanding

Why keep a max-heap of the closest points rather than a min-heap?

K Closest Points to Origin

K Closest Points to Origin

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Heap and Priority Queue