K Closest Points to Origin
Understanding the Problem
We have a list of 2D points and need to find the k points closest to the origin (0, 0). The Euclidean distance from a point (x, y) to the origin is sqrt(x^2 + y^2). We only care about the relative ordering of distances, not the actual values, so we can compare x^2 + y^2 directly and skip the square root. The square root function is monotonically increasing, so sqrt(a) < sqrt(b) exactly when a < b, which means ordering by squared distance gives the same result as ordering by true distance.
The answer can be returned in any order. We do not need a fully sorted result, only any k elements that are the smallest. That allows approaches faster than a full sort.
Key Constraints:
-10^4 <= xi, yi <= 10^4-> The largest squared distance is 10^4^2 + 10^4^2 = 2 10^8, which fits in a signed 32-bit integer (max ~2.1 10^9). Distances never overflowint, so there is no need forlong.1 <= k <= points.length <= 10^4-> k is always a valid count, so no bounds checking is needed. With n up to 10,000, an O(n log n) sort runs fine, but the "any order" allowance leaves room for O(n log k) and average O(n) solutions.
Approach 1: Sort by Distance
Intuition
Compute the squared distance for every point, sort the entire array by that distance, and take the first k elements. Sorting produces a fully ordered array, which is more than the problem asks for. We only need the k smallest, not all n in order, but sorting gets us there with no extra logic.
Algorithm
- Sort the
pointsarray using a custom comparator that comparesx^2 + y^2for each point. - Return the first
kelements of the sorted array.
Example Walkthrough
Code
- Time Complexity: O(n log n). Sorting the entire array of n points dominates the cost. Extracting the first k elements is O(k).
- Space Complexity: O(log n). The space used by the sorting algorithm's internal stack.
Sorting touches all n points even though we only need the k smallest. The next approach keeps only the k closest points seen so far, lowering the cost when k is much smaller than n.
Approach 2: Max-Heap of Size K
Intuition
Instead of sorting the entire array, maintain a max-heap of size k. The heap holds the k closest points seen so far, with the farthest of those k at the top.
Scanning through the points, compare each new point's distance against the heap's maximum. If the new point is closer, remove the farthest point and insert the new one. If the heap has fewer than k elements, add the point directly. The farthest-on-top ordering makes the comparison against the current worst candidate an O(1) lookup.
The invariant is that after processing the first i points, the heap holds the k closest among those i (or all of them if i < k). When point i+1 arrives, either it is closer than the current farthest, in which case it belongs in the top k and the farthest is evicted, or it is not closer, in which case it cannot displace any of the current k. Removing the farthest is safe: a point removed because k other points are closer can never re-enter, since later points only shrink the set of distances that beat it.
Algorithm
- Create a max-heap (priority queue ordered by descending distance).
- For each point in the array:
- If the heap has fewer than k elements, add the point.
- Otherwise, if the point's squared distance is less than the heap's maximum, remove the max and add this point.
- Extract all k points from the heap and return them.
Example Walkthrough
Code
- Time Complexity: O(n log k). We process each of the n points. Each heap operation is O(log k) since the heap never exceeds size k.
- Space Complexity: O(k). The heap holds at most k elements at any time.
The heap wins when k is small, but every element still costs O(log k). The next approach drops the per-element log factor by partitioning the array around the k-th smallest distance, reaching O(n) on average.
Approach 3: Quickselect
Intuition
The task reduces to finding the k smallest distances and returning those points, in any order. Quickselect does this without fully sorting: it rearranges the array so that the element at index k sits in its final sorted position, with every smaller element to its left and every larger element to its right. Once index k is settled, the first k slots hold the answer regardless of their internal order.
Quickselect chooses a pivot, partitions the array around it (smaller distances go left, larger go right), and checks where the pivot landed. If the pivot is at index k, the first k elements are the answer. If it landed past k, recurse on the left part. If before k, recurse on the right part.
The savings come from recursing on only one side. Quicksort recurses on both halves for O(n log n) total work. Quickselect descends into one half, roughly halving the remaining work each step: n + n/2 + n/4 + ... = 2n = O(n) on average.
Algorithm
- Define a helper function
quickSelect(points, left, right, k). - Pick a random pivot index between
leftandright. - Partition the array: move points with smaller distance to the left of the pivot, larger to the right.
- If the pivot index equals k, return (the first k elements are the answer).
- If the pivot index is less than k, recurse on the right portion.
- If the pivot index is greater than k, recurse on the left portion.
- Return the first k elements of the (partially sorted) array.
Example Walkthrough
Code
- Time Complexity: O(n) average, O(n^2) worst case. On average, each partition halves the problem size, giving O(n + n/2 + n/4 + ...) = O(2n) = O(n). The worst case occurs only when pivots repeatedly land at an extreme; random pivot selection makes that unlikely.
- Space Complexity: O(log n) average for the recursion stack, since the problem size roughly halves each call. The worst case is O(n) when partitions are maximally unbalanced. An iterative loop instead of recursion would reduce this to O(1).