179. K Closest Points to the Origin

Given n points on a 2D plane (as x y pairs) and a value k, find the k points closest to the origin (0, 0) by Euclidean distance. Print them ordered by ascending distance; break ties by smaller x, then by smaller y. Print each point's x and y, space-separated, in that order, all on one line.

Input: The first line contains an integer n, the number of points. Each of the next n lines contains two space-separated integers x and y, a point's coordinates. The final line contains the integer k. Output: Print the k closest points to the origin, each point's x and y space-separated, all on one line, ordered by ascending distance (ties broken by smaller x, then smaller y).

1 <= k <= n <= 10^5

Comparing squared distances instead of true distances is a simple but broadly useful trick anywhere distances need to be COMPARED (not displayed) - it avoids floating-point operations entirely while preserving the correct relative order.

Find the k points closest to the origin (0,0) among a given set of 2D points. Brute force: Compute every point's distance, sort ALL points by distance, and take the first k - this costs O(n log n), more than necessary when only the k closest (not a full ordering) are needed. Optimised: A max-heap capped at size k only ever needs to track the k CLOSEST points seen so far - any point farther than the heap's current farthest can be immediately discarded, reducing the sort cost from O(n log n) down to O(n log k).

Compute each point's squared distance (avoiding the sqrt, which doesn't change relative order) and run Quickselect to partition the array so the k smallest distances land in the first k positions, without fully sorting the rest of the array - this takes expected linear time since, like in the classic kth-smallest problem, only one side of each partition needs to be recursed into. Finally, sort just those k partitioned points by distance and the tie-break rule to produce the ordered output. This avoids the log(k) heap-maintenance overhead entirely for the selection phase, needing only O(k log k) work for the final small sort. Time: O(n) average + O(k log k) Space: O(k)

Repeat n times: scan through all remaining points, find the one with the smallest remaining Euclidean distance to the origin (applying the tie-break rule when distances match), and move it to the output list. This produces the correctly ordered list of the k closest points by explicitly selecting the next-closest point one at a time, but re-scanning the entire remaining set for every selection is wasteful. Time: O(n*k) Space: O(n)

Maintain a max-heap (ordered by distance, with the tie-break rule as a secondary key) that holds at most k points: push each point's (distance, x, y) in, and whenever the heap exceeds size k, pop the farthest point off. After processing all n points, the heap contains exactly the k closest; pop everything off and sort those k entries by distance (and the tie-break rule) to produce the final ordered answer. This avoids ever comparing against the full remaining set repeatedly, paying only O(log k) per point instead of O(n) per selection. Time: O(n log k + k log k) Space: O(k)

1. Compute each point's SQUARED distance (x² + y²) - this avoids floating-point square roots entirely while giving the exact same relative ordering. 2. Maintain a max-heap of size k, keyed by squared distance - push each point in, and evict the farthest one whenever the heap exceeds size k. 3. Empty the final heap, sorted by ascending distance (with the given tie-breaking rule for equal distances).

Time: O(n log k) - each of the n points triggers at most one push and one pop on a heap of size at most k. Space: O(k), for the heap.

k = 1 (as in the example), k = n (all points returned, sorted by distance), and points equidistant from the origin requiring the x/y tie-break.

Be ready to explain WHY squared distance (rather than actual Euclidean distance with a square root) is used - since square root is a monotonically increasing function, comparing squared distances gives the exact same ordering while avoiding floating-point precision issues and unnecessary computation.