Sponsored
Sponsored
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.
1var kClosest = function(points, k) {
2 points.sort((a, b) => (a[0]**2 + a[1]**2) - (b[0]**2 + b[1]**2));
3 return points.slice(0, k);
4};This JavaScript solution sorts the points by squared distances using Array.sort, then slices the array to get the first k points.
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.
1Using a priority queue (from a library like collections), this JavaScript solution maintains a max-heap containing the closest points, dequeuing the largest whenever k is exceeded.