885661. K Closest Points to Origin
Medium
K Closest Points to Origin
Summary
Given a list of n points in 2D space, find the k closest points to the origin (0, 0). The problem involves sorting and priority queue concepts, as we need to efficiently identify the closest points.
Detailed Explanation
The approach is to first calculate the distance of each point from the origin. Then, use a priority queue (min-heap) to keep track of the k closest points. This way, we can efficiently remove the farthest point and add a new one if necessary.
Here's a step-by-step breakdown:
- Initialize an empty min-heap (priority queue).
- Iterate through each point
(x, y)in the input list. - Calculate the distance
dfrom the origin using the Euclidean distance formula:d = sqrt(x^2 + y^2). - Add the point and its corresponding distance to the priority queue (min-heap).
- Once all points have been processed, extract the top
kelements from the priority queue, which represent thekclosest points to the origin. - Return these
kpoints.
Time Complexity Analysis: The time complexity is O(n log n) due to the sorting and priority queue operations.
Space Complexity Analysis:
The space complexity is O(k) for storing the k closest points in the min-heap (priority queue).
Optimized Solutions
Java
import java.util.*;
class Point {
int x, y;
double dist;
public Point(int x, int y) {
this.x = x;
this.y = y;
this.dist = Math.sqrt(x * x + y * y);
}
public static void main(String[] args) {
List<Point> points = Arrays.asList(new Point(1, 2), new Point(-3, -4), ...);
int k = 2;
// Calculate the distance and store in a min-heap
PriorityQueue<Point> pq = new PriorityQueue<>();
for (Point p : points) {
pq.add(p);
}
// Extract the top 'k' elements from the min-heap
List<Point> closestPoints = new ArrayList<>();
for (int i = 0; i < k; i++) {
closestPoints.add(pq.poll());
}
// Print the 'k' closest points
System.out.println(closestPoints);
}
}