K Closest Points to Origin — LeetCode 973 Walkthrough

K Closest Points to Origin (LeetCode #973) is one of the cleanest examples of the Top K pattern in action. Instead of finding the most frequent elements or the kth largest number, you are finding the K points nearest to the origin (0, 0) in a 2D plane. The underlying algorithmic toolkit is identical — sort, heap, or quickselect — with Euclidean distance as the comparator.

If you have already solved Top K Frequent Elements (#347) or Kth Largest Element (#215), this problem will feel familiar. The only new ingredient is computing distance from coordinates. Once you see the connection, k closest points to origin leetcode becomes a straightforward application of patterns you already know.

This walkthrough covers three approaches — sort, max-heap, and quickselect — so you can choose the right tool depending on the interview context and constraints.

You are given an array of points where points[i] = [xi, yi] represents a point on the 2D plane, and an integer k. Return the k closest points to the origin (0, 0). The answer can be returned in any order, and distance is measured using standard Euclidean distance.

Euclidean distance from a point (x, y) to the origin is sqrt(x^2 + y^2). However, since you only need to compare relative distances, you can skip the square root entirely and compare x^2 + y^2 directly. The square root function is monotonically increasing, so if dist_squared(A) < dist_squared(B), then dist(A) < dist(B). This avoids floating-point precision issues and is faster.

The problem guarantees that the answer is unique — there will not be ties that make the result ambiguous. Points can have negative coordinates, but squaring handles that naturally.

The most straightforward leetcode 973 solution is to sort the entire array by squared distance and return the first k elements. Compute x^2 + y^2 for each point, sort in ascending order, and slice the first k results.

This runs in O(n log n) time and O(n) space for the sort. It is simple, correct, and perfectly acceptable for most interviews as a starting point. Mention it, then offer to optimize.

The key insight is that you do not need the full sorted order — you only need the k smallest distances. This observation opens the door to more efficient approaches.

A max-heap of size k lets you maintain the k closest points seen so far as you iterate through the array. For each point, push it onto the heap. If the heap size exceeds k, pop the farthest point (the max). After processing all points, the heap contains exactly the k closest.

This approach runs in O(n log k) time because each heap operation is O(log k), and you perform n of them. When k is much smaller than n, this is a meaningful improvement over sorting. Space is O(k) for the heap itself.

In JavaScript, there is no built-in heap, so you would implement a simple max-heap or use a library. In Python, you can use heapq with negated distances to simulate a max-heap. In Java, use a PriorityQueue with a custom comparator.

Quickselect is the same partitioning algorithm behind quicksort, but you only recurse into the half that contains the kth element. Pick a pivot, partition points so that everything with smaller distance is on the left and larger distance is on the right. If the pivot lands at index k, you are done — the first k elements are the answer.

The average time complexity is O(n), making this the fastest approach for large inputs. However, the worst case is O(n^2) when the pivot choice is consistently bad — just like quicksort. Randomizing the pivot brings the expected case back to O(n) and makes worst-case behavior astronomically unlikely.

Quickselect modifies the array in place, so space complexity is O(1) beyond the recursion stack. The trade-off is that it is harder to implement correctly in an interview setting, so many candidates present the heap approach first and mention quickselect as an optimization.

When k equals n, return the entire array — no sorting or selection is needed. When k equals 1, you only need the single closest point, which is a simple linear scan in O(n).

Points can have negative coordinates like [-3, -4], but squaring eliminates the sign so distance computation works identically. Multiple points can share the same distance from the origin, but the problem guarantees a unique answer set, so ties do not create ambiguity.

Watch for integer overflow if coordinates are large. In most interview settings with standard constraints (coordinates up to 10^4), x^2 + y^2 fits comfortably in a 32-bit integer. For safety in production code, use 64-bit integers or check the constraint bounds.

This problem reinforces the Top K pattern — one of the most versatile patterns in coding interviews. The core idea is always the same: you have n items, a scoring function, and you want the top (or bottom) k. The only thing that changes between problems is the comparator.

For Kth Largest Element (#215), the comparator is the element value itself. For Top K Frequent Elements (#347), it is the frequency count. For k closest points to origin leetcode, it is the squared Euclidean distance. Recognizing this shared structure lets you solve new Top K variants instantly.

Practice all three problems back to back on YeetCode to lock in the pattern. The flashcard-based approach helps you internalize the heap template and quickselect partition logic so they become second nature before your next interview.