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 <= 104In #973 K Closest Points to Origin, the goal is to return the k points that are closest to the origin (0,0). Distance is typically compared using the squared Euclidean distance x^2 + y^2 to avoid unnecessary square root calculations.
A straightforward approach is to compute the distance for every point and sort the array by this value, then return the first k points. While simple, sorting processes the entire dataset even though only k elements are required.
A more efficient method uses a max heap (priority queue) of size k. Iterate through the points and maintain the k closest seen so far. If a new point is closer than the heap's maximum distance, replace it.
For optimal performance, Quickselect can partition the array similarly to QuickSort and place the k closest points in the first portion of the array. This reduces average complexity compared to full sorting.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Sorting all points | O(n log n) | O(1) or O(n) depending on sort |
| Max Heap of size k | O(n log k) | O(k) |
| Quickselect | Average: O(n), Worst: O(n^2) | O(1) |
NeetCode
This approach leverages the simplicity of sorting the list of points based on their distance from the origin. After sorting, the first k points will be the closest ones. The key is to use the squared Euclidean distance to avoid the computational overhead of square root operations.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) since the sorting is done in-place.
1from typing import List
2
3def kClosest(points: List[List[int]], k: int) -> List[List[int]]:
4 points.sort(key=lambda x: x[0]**2 + x[1]**2)
5 return points[:k]
6This Python solution uses the sort() function with a key that computes squared distances. The first k elements post-sort are returned.
The Max-Heap approach uses a priority queue to maintain the k closest points seen so far. By using a max-heap, we can efficiently insert new points and potentially evict the farthest point if it is further than any encountered point, leading to a reduced time complexity for finding the k closest points.
Time Complexity: O(n log k) since each insertion/extraction in the heap takes O(log k) time.
Space Complexity: O(k) for the heap storage.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this problem is frequently asked in technical interviews at large tech companies. It tests knowledge of heaps, partitioning algorithms like Quickselect, and efficient handling of geometric data.
A max heap (priority queue) of size k is commonly used. It keeps track of the k closest points while scanning the array and removes the farthest point whenever the heap exceeds size k.
The optimal average-case approach is Quickselect, which partitions the array so that the k closest points appear in the first k positions. This avoids fully sorting the array and typically runs in O(n) time. It is especially efficient when k is much smaller than n.
Squared distance avoids computing square roots, which are unnecessary when only comparing relative distances. Since the square root function is monotonic, comparing x^2 + y^2 values gives the same ordering.
This C solution maintains a max-heap of size k using a custom struct. It inserts each point by distance until the max-heap is full. For subsequent points, it compares distances and potentially evicts the farthest point if a closer point is found.