Watch 10 video solutions for K Closest Points to Origin, a medium level problem involving Array, Math, Divide and Conquer. This walkthrough by NeetCode has 133,518 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).
The distance between two points on the X-Y plane is the Euclidean distance (i.e., √(x1 - x2)2 + (y1 - y2)2).
You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in).
Example 1:
Input: points = [[1,3],[-2,2]], k = 1 Output: [[-2,2]] Explanation: The distance between (1, 3) and the origin is sqrt(10). The distance between (-2, 2) and the origin is sqrt(8). Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin. We only want the closest k = 1 points from the origin, so the answer is just [[-2,2]].
Example 2:
Input: points = [[3,3],[5,-1],[-2,4]], k = 2 Output: [[3,3],[-2,4]] Explanation: The answer [[-2,4],[3,3]] would also be accepted.
Constraints:
1 <= k <= points.length <= 104-104 <= xi, yi <= 104Problem Overview: You are given an array of 2D points and an integer k. Each point represents (x, y) on a Cartesian plane. Return the k points closest to the origin (0,0). Distance is measured using Euclidean distance, but you only need the squared distance x*x + y*y for comparisons.
Approach 1: Sort and Select (O(n log n) time, O(1) or O(n) space)
The simplest strategy computes the squared distance for every point and sorts the array by that value. After sorting, the first k points are the closest. Sorting guarantees correct ordering but does more work than required because the entire list is ordered even though you only need the smallest k elements. This approach relies on standard sorting algorithms and is often the easiest implementation across languages.
Approach 2: Max-Heap (Priority Queue) (O(n log k) time, O(k) space)
A more efficient method maintains a max-heap of size k. Iterate through all points, compute the squared distance, and push the point into the heap. If the heap size exceeds k, remove the farthest element (the heap root). The heap always stores the k closest points seen so far. Each insertion or removal costs O(log k), which leads to O(n log k) total time. This method is common in interview problems involving streaming or partial selection and uses a heap (priority queue) to maintain the top candidates efficiently.
Approach 3: Quickselect (Average O(n) time, O(1) extra space)
Quickselect applies the partition logic from quicksort to position the k-th closest distance in the correct place. Choose a pivot, partition the points so those with smaller distances move to the left, and recursively process only the relevant side. Once the pivot index equals k, the first k elements contain the closest points (order does not matter). This technique falls under divide and conquer and avoids fully sorting the array. Average runtime is O(n), though the worst case is O(n^2). In practice it performs very well and is the optimal theoretical solution.
Recommended for interviews: Start with the sorting idea to show clarity, then move to the max-heap solution since it improves complexity to O(n log k) and is widely accepted in interviews. If the interviewer pushes for optimal performance, implement Quickselect for average O(n) time. Demonstrating both heap and selection algorithms shows strong familiarity with partial sorting problems.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sort and Select | O(n log n) | O(1)–O(n) | Simple implementation when constraints are small or readability matters more than optimal performance |
| Max-Heap (Priority Queue) | O(n log k) | O(k) | Best practical approach when k is much smaller than n or when processing elements incrementally |
| Quickselect | Average O(n), Worst O(n^2) | O(1) | Optimal selection algorithm when you only need the k smallest elements without full sorting |