K Closest Points to Origin
Last Updated: March 29, 2026
Understanding the Problem
We have a list of 2D points and need to find the k points that are closest to the origin (0, 0). The Euclidean distance from a point (x, y) to the origin is sqrt(x^2 + y^2). But here is a useful observation: since we only care about relative ordering of distances (not the actual distance values), we can compare x^2 + y^2 directly and skip the square root entirely. Squaring preserves the ordering because the square root function is monotonically increasing.
The problem says the answer can be returned in any order, which is a strong hint. We do not need a fully sorted result, just any k elements that happen to be the smallest. This opens the door to approaches that are faster than a full sort.
Key Constraints:
1 <= k <= points.length <= 10^4-> With n up to 10,000, O(n log n) sorting is comfortable. But the "any order" hint suggests we can do better.-10^4 <= xi, yi <= 10^4-> Squared distance x^2 + y^2 is at most 2 * 10^8, which fits in a 32-bit integer. No overflow concerns.k <= points.length-> k is always valid, no edge case handling needed.
Approach 1: Sort by Distance
Intuition
The most direct approach: compute the squared distance for every point, sort the entire array by that distance, and take the first k elements. Since we only need relative ordering, we can sort by x^2 + y^2 without computing the actual square root.
This is clean and easy to get right. Sorting gives us a fully ordered result, which is more than we need (we only need the k smallest, not all n in order), but it works.
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.
This approach works but sorts all n points when we only need the k smallest. What if we maintained just the top k closest points as we scanned the array?
Approach 2: Max-Heap of Size K
Intuition
Instead of sorting the entire array, we can maintain a max-heap (priority queue) of size k. The heap holds the k closest points we have seen so far, with the farthest of those k at the top.
As we scan through the points, we compare each new point's distance against the heap's maximum. If the new point is closer, we remove the farthest point and insert the new one. If the heap has fewer than k elements, we just add the point directly.
The max-heap acts as a sliding window over the k closest points. At any moment, the heap contains the k smallest distances seen so far. The max-heap property ensures the largest among those k is always at the top, making it O(1) to compare against new candidates. When a closer point arrives, it displaces the farthest point in our current set.
Once a point is kicked out of the heap, it can never come back. If point P was removed because point Q was closer, then P is farther than at least k other points and cannot be in the answer.
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 approach is better when k is small, but we still pay O(log k) per element. What if we could partition the array around the k-th smallest distance instead?
Approach 3: Quickselect
Intuition
The problem boils down to finding the k-th smallest distance and returning everything at or below that threshold. This is exactly what the quickselect algorithm does: it partially sorts an array so that the element at position k is in its final sorted position, with all smaller elements to its left and all larger elements to its right.
Quickselect works by choosing a pivot, partitioning the array around it (all elements with smaller distance go left, larger go right), and then checking where the pivot landed. If the pivot is at index k, we are done. If it is past k, recurse on the left half. If it is before k, recurse on the right half.
The efficiency comes from only recursing on one side. Unlike quicksort which recurses on both halves (total work: O(n log n)), quickselect recurses on one half, cutting the problem size roughly in half each time: n + n/2 + n/4 + ... = O(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). Random pivot selection makes worst case extremely unlikely.
- Space Complexity: O(log n) average for recursion stack. Each recursive call reduces the problem size by roughly half, so the recursion depth is O(log n) on average.