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 <= 104This 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.
This C code uses the qsort function to sort the points array based on the calculated squared distances. It extracts the first k elements and returns them as the closest points.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) since the sorting is done in-place.
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.
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.
C++
Java
Python
C#
JavaScript
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.
| Approach | Complexity |
|---|---|
| Sort and Select | Time Complexity: O(n log n) due to sorting. |
| Max-Heap (Priority Queue) | Time Complexity: O(n log k) since each insertion/extraction in the heap takes O(log k) time. |
K Closest Points to Origin - Heap / Priority Queue - Leetcode 973 - Python • NeetCode • 107,738 views views
Watch 9 more video solutions →Practice K Closest Points to Origin with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor