K-Closest Points to a given Target Point in Java
The K-Closest Points to a Given Target Point problem involves finding the K points from a set of points that are closest to a specified target point in a 2D or 3D space.
Problem Statement:
Given an array of points in a 2D plane, find the K points that are closest to a specified target point.
The distance between two points is calculated using the Euclidean distance formula: √((x2-x1)^2+(y2-y1)^2).
Example 1:
Input:
Points=[(1,3),(5,2),(8,7),(2,6)] Target=(3,4) K=2
Output:
[(5,2),(1,3)]
Explanation:
In this scenario we are presented with an array of points along with a designated target point. Our objective is to determine the K points that exhibit the closest proximity to the target point. To achieve this we compute the squared distances between the target point and each of the provided points.
Squared distance from (1, 3) to target = 2^2 + 1^2 = 5
Squared distance from (5, 2) to target = 2^2 + 2^2 = 8
Squared distance from (8, 7) to target = 5^2 + 3^2 = 34
Squared distance from (2, 6) to target = 1^2 + 2^2 = 5
The two closest points are (5,2) and (1,3) with squared distances 5 and 5 respectively. Therefore the output is [(5,2),(1,3)].
Example 2:
Input:
Points=[(0,0),(1,1),(2,2),(3,3)] Target=(0,2) K=3
Output:
[(1,1),(0,0),(2,2)]
Explanation: For this example, we have a set of points and a target point. We are tasked with finding the K closest points to the target. The squared distances from the target point to each of the given points are calculated as follows:
- Squared distance from (0, 0) to target = 2^2 + 2^2 = 8
- Squared distance from (1, 1) to target = 1^2 + 1^2 = 2
- Squared distance from (2, 2) to target = 2^2 + 0^2 = 4
- Squared distance from (3, 3) to target = 3^2 + 1^2 = 10
The three closest points are (1, 1), (0, 0), and (2, 2) with squared distances 2, 8, and 4 respectively. Therefore, the output is [(1, 1), (0, 0), (2, 2)].
Example 3:
Input:
Points=[(10,5),(2,9),(7,8),(4,3)] Target=(6,7) K=1
Output:
[(4,3)]
Explanation:
In this example we are given an array of points and a target point. Our goal is to identify the K closest points to the target. The squared distances from the target point to each of the given points are computed as follows:
Squared distance from (10, 5) to target = 4^2 + 2^2 = 20
Squared distance from (2, 9) to target = 4^2 + 2^2 = 20
Squared distance from (7, 8) to target = 1^2 + 1^2 = 2
Squared distance from (4, 3) to target = 2^2 + 4^2 = 20
The closest point to the target is (4, 3) with a squared distance of 20. Therefore, the output is [(4, 3)].
Approach 1: Using Max Heap (Priority Queue)
ALGORITHM:
Step 1: Create a Point class with x and y coordinates, a constructor to initialize these coordinates, a method squaredDistance() to calculate squared distance from the origin, and a toString() method to display the point.
Step 2: Implement a PointComparator class that implements the Comparator interface. It should take a target point as input.
Step 3: In the PointComparator class, implement the compare() method:
Step 3.1: Calculate and compare the squared distances between p1 and p2 from the target point.
Step 3.2: Return the result of comparing these squared distances.
Create a KClosestPoints class to encapsulate the main logic for finding closest points.
Step 4: Define a method kClosest() in the KClosestPoints class, taking points, target, and k as parameters.
Step 5: Inside the kClosest() method, initialize a PriorityQueue named maxHeap using the PointComparator and the given target. This queue will hold the closest points.
Step 6: Iterate through each point in the points array:
Step 7: Add the current point to the maxHeap using maxHeap.offer(point).
Step 8: If the size of maxHeap exceeds k, remove the point with the largest squared distance using maxHeap.poll().
Step 9: After processing all points, create an empty ArrayList named result to store the final closest points.
Step 10: Loop until the maxHeap is not empty:
Step 10.1: Remove the point with the largest squared distance from maxHeap using maxHeap.poll().
Step 10.2: Add the removed point to the result list.
Step 11: Reverse the result list using Collections.reverse(result) to get the closest points in ascending order of distance.
Step 12: Return the result list containing the k closest points.
Step 13: In the main() method:
Step 13.1: Create an instance of KClosestPoints named solution.
Step 13.2: Define three example cases (Example 1, Example 2, Example 3):
For each example:
Step 13.3: Create an array of Point objects representing the points.
Step 13.4: Create a target point.
Step 13.5: Set the value of k.
Step 14: Apply the kClosest() method to each example case, passing in the appropriate points, target, and k.
Step 15: Print the results of each example using System.out.println().
Step 16: Run the program to see the output for each example.
Step 17: The algorithm calculates the k closest points to the given target point using a priority queue and custom comparator.
Step 18: The output displays the closest points for each example case.
Step 19: The algorithm leverages data structures effectively to solve proximity-based problems.
Step 20: The time complexity depends on the number of points and is mainly determined by the operations on the priority queue.
Implementation:
The Implementation of the above steps given below
FileName: KClosestPoints.java
import java.util.*; class Point { int x,y; Point(int x,int y) { this.x=x; this.y=y; } int squaredDistance() { return x*x+y*y; } public String toString() { return "("+x+","+y+")"; } } class PointComparator implements Comparator<Point> { Point target; PointComparator(Point target) { this.target = target; } public int compare(Point p1,Point p2) { return Integer.compare(p2.squaredDistance(),p1.squaredDistance()); } } public class KClosestPoints { public List<Point> kClosest(Point[] points, Point target, int k) { PriorityQueue<Point> maxHeap = new PriorityQueue<>(new PointComparator(target)); for (Point point : points) { maxHeap.offer(point); if (maxHeap.size() > k) { maxHeap.poll(); } } List<Point> result = new ArrayList<>(); while (!maxHeap.isEmpty()) { result.add(maxHeap.poll()); } Collections.reverse(result); return result; } public static void main(String[] args) { KClosestPoints solution = new KClosestPoints(); // Example 1 Point[] points1 = { new Point(1, 3), new Point(5, 2), new Point(8, 7), new Point(2, 6) }; Point target1 = new Point(3, 4); int k1 = 2; List<Point> closestPoints1 = solution.kClosest(points1, target1, k1); System.out.println("Example 1: " + closestPoints1); // Example 2 Point[] points2 = { new Point(0, 0), new Point(1, 1), new Point(2, 2), new Point(3, 3) }; Point target2 = new Point(0, 2); int k2 = 3; List<Point> closestPoints2 = solution.kClosest(points2, target2, k2); System.out.println("Example 2: " + closestPoints2); // Example 3 Point[] points3 = { new Point(10, 5), new Point(2, 9), new Point(7, 8), new Point(4, 3) }; Point target3 = new Point(6, 7); int k3 = 1; List<Point> closestPoints3 = solution.kClosest(points3, target3, k3); System.out.println("Example 3: " + closestPoints3); } }
Output:
Example 1: [(1, 3), (5, 2)] Example 2: [(0, 0), (1, 1), (2, 2)] Example 3: [(4, 3)]
Complexity Analysis:
Time Complexity:
Constructing the max heap with the custom comparator: O(n * log k), where n is the number of points and k is the desired number of closest points. Iterating through each point and operations within the loop: O(n * log k), same as above.
Constructing the result list and reversing: O(k * log k), where k is the desired number of closest points.Overall time complexity: O(n * log k).
Space Complexity:
Max heap (priority queue): O(k), as it holds the k closest points and the Result list: O(k), for storing the closest points.Therfore, Overall space complexity: O(k).
Approach 2: Using Sorting
ALGORITHM:
Step 1: Define a Point class with x and y coordinates, along with methods to calculate squared distance and represent the point as a string.
Step 2: Create a KClosestPoints class to encapsulate the main logic for finding closest points.
Step 3: Define a kClosest() method that takes an array of points, a target point, and the value of k.
Step 4: Inside the kClosest() method:
Step 4.1: Sort the points array based on squared distances using Arrays.sort() and a comparator that compares squared distances.
Step 4.2: Create an empty ArrayList named result to store the final closest points.
Step 5: Iterate through the sorted points array up to the first k elements:
Step 5.1: Add each point to the result list.
Step 6: Return the result list containing the k closest points.
Step 7: In the main() method:
Step 7.1: Create an instance of KClosestPoints named solution.
Step 8: Define three example cases (Example 1, Example 2, Example 3):
Step 8.1: For each example:
Step 8.1.1: Create an array of Point objects representing the points.
Step 8.1.2: Create a target point.
Step 8.1.3: Set the value of k.
Step 9: Apply the kClosest() method to each example case, passing in the appropriate points, target, and k.
Step 10: Print the results of each example using System.out.println().
Step 11: Run the program to see the output for each example.
Implementation:
The Implementation of the above steps given below
FileName: KClosestPoints.java
import java.util.*; class Point { int x, y; Point(int x, int y) { this.x = x; this.y = y; } int squaredDistance() { return x * x + y * y; } public String toString() { return "(" + x + ", " + y + ")"; } } public class KClosestPoints { public List<Point> kClosest(Point[] points, Point target, int k) { Arrays.sort(points, Comparator.comparingInt(point -> point.squaredDistance())); List<Point> result = new ArrayList<>(); for (int i = 0; i < k; i++) { result.add(points[i]); } return result; } public static void main(String[] args) { KClosestPoints solution = new KClosestPoints(); // Example 1 Point[] points1 = { new Point(1, 3), new Point(5, 2), new Point(8, 7), new Point(2, 6) }; Point target1 = new Point(3, 4); int k1 = 2; List<Point> closestPoints1 = solution.kClosest(points1, target1, k1); System.out.println("Example 1: " + closestPoints1); // Example 2 Point[] points2 = { new Point(0, 0), new Point(1, 1), new Point(2, 2), new Point(3, 3) }; Point target2 = new Point(0, 2); int k2 = 3; List<Point> closestPoints2 = solution.kClosest(points2, target2, k2); System.out.println("Example 2: " + closestPoints2); // Example 3 Point[] points3 = { new Point(10, 5), new Point(2, 9), new Point(7, 8), new Point(4, 3) }; Point target3 = new Point(6, 7); int k3 = 1; List<Point> closestPoints3 = solution.kClosest(points3, target3, k3); System.out.println("Example 3: " + closestPoints3); } }
Output:
Example 1: [(1, 3), (5, 2)] Example 2: [(0, 0), (1, 1), (2, 2)] Example 3: [(4, 3)]
Complexity Analysis:
Time Complexity:
Sorting the array of points takes O(n*log n) time where n is the number of points and Extracting the k closest points from the taken care of array takes O(k) time.Overall time complexity is dominated by the sorting operation, making it O(n * log n).
Space Complexity:
The space required for storing the array of points is O(n) and the space required for the result list to store the k closest points is O(k). Other variables and data structures used in the algorithm require negligible space in comparison. Overall space complexity is O(n) where n is the number of points.
Approach 3: Divide and Conquer (QuickSelect)
ALGORITHM:
Step 1: Define a Point class with x and y coordinates, a constructor, methods to calculate squared distance and represent the point as a string.
Step 2; Create a KClosestPoints class to encapsulate the main logic for finding closest points.
Step 3: Define a kClosest() method that takes an array of points, a target point, and the value of k.
Step 4: Inside the kClosest() method:
Step 4.1: Call the quickSelect() method to rearrange the points array based on the kth closest point.
Step 4.2: Return a list containing the first k points using Arrays.asList() and subList().
Step 5: Implement a private quickSelect() method that performs the QuickSelect algorithm to partition and find the kth closest point.
Step 5.1: If the left index is less than the right index:
Step 5.1.1: Find the pivot index using the partition() method.
Step 5.1.2: If the pivot index is equal to k, the kth closest point is found.
Step 5.1.3: Otherwise, recursively call quickSelect() on the appropriate partition based on the pivot index and k.
Step 6: Implement a private partition() method that rearranges the points array based on squared distances from the pivot distance.
Step 6.1: Initialize pivotIndex as left.
Step 6.2: Use the squared distance of the right element as the pivot distance.
Step 6.3: Iterate through the array from left to right-1:
Step 6.3.1: If the squared distance of the current point is less than or equal to the pivot distance, swap it with the element at pivotIndex and increment pivotIndex.
Step 6.4: Swap the pivot element (at pivotIndex) with the right element.
Step 6.5: Return the pivot index.
Step 7: Implement a private swap() method to swap two elements in the points array.
Step 8: In the main() method:
Step 8.1: Create an instance of KClosestPoints named solution.
Step 9: Define three example cases (Example 1, Example 2, Example 3):
Step 9.1: For each example:
Step 9.1.2: Create an array of Point objects representing the points.
Step 9.1.3: Create a target point.
Step 9.1.4: Set the value of k.
Step 10: Apply the kClosest() method to each example case, passing in the appropriate points, target, and k.
Step 11: Print the results of each example using System.out.println().
Step 12: Run the program to see the output for each example.
Implementation:
The implementation of the above steps given below.
FileName: KClosestPoints.java
import java.util.*; class Point { int x,y; Point(int x,int y) { this.x=x; this.y=y; } int squaredDistance() { return x*x+y*y; } public String toString() { return "("+x+","+y+")"; } } public class KClosestPoints { public List<Point> kClosest(Point[] points, Point target, int k) { quickSelect(points, 0, points.length - 1, k); return Arrays.asList(points).subList(0, k); } private void quickSelect(Point[] points, int left, int right, int k) { if (left < right) { int pivotIndex = partition(points, left, right); if (pivotIndex == k) { return; } else if (pivotIndex < k) { quickSelect(points, pivotIndex + 1, right, k); } else { quickSelect(points, left, pivotIndex - 1, k); } } } private int partition(Point[] points, int left, int right) { int pivotIndex = left; int pivotDist = points[right].squaredDistance(); for(int i=left;i<right;i++) { if (points[i].squaredDistance() <= pivotDist) { swap(points, i, pivotIndex); pivotIndex++; } } swap(points, pivotIndex, right); return pivotIndex; } private void swap(Point[] points, int i, int j) { Point temp = points[i]; points[i] = points[j]; points[j] = temp; } public static void main(String[] args) { KClosestPoints solution = new KClosestPoints(); // Example 1 Point[] points1 = { new Point(1, 3), new Point(5, 2), new Point(8, 7), new Point(2, 6) }; Point target1 = new Point(3, 4); int k1 = 2; List<Point> closestPoints1 = solution.kClosest(points1, target1, k1); System.out.println("Example 1: " + closestPoints1); // Example 2 Point[] points2 = { new Point(0, 0), new Point(1, 1), new Point(2, 2), new Point(3, 3) }; Point target2 = new Point(0, 2); int k2 = 3; List<Point> closestPoints2 = solution.kClosest(points2, target2, k2); System.out.println("Example 2: " + closestPoints2); // Example 3 Point[] points3 = { new Point(10, 5), new Point(2, 9), new Point(7, 8), new Point(4, 3) }; Point target3 = new Point(6, 7); int k3 = 1; List<Point> closestPoints3 = solution.kClosest(points3, target3, k3); System.out.println("Example 3: " + closestPoints3); } }
Output:
Example 1: [(1,3), (5,2)] Example 2: [(0,0), (1,1), (2,2)] Example 3: [(4,3)]
Complexity Analysis:
Time Complexity:
The QuickSelect algorithm has an average-case time complexity of O(n), where n is the number of points in the array and the partition step takes O(n) time in each recursive call. In each recursion the array is divided into two sub arrays to find the Kth smallest element which results in a logarithmic number of recursive calls. Overall the algorithm time complexity can be considered as O(n) on average but in the worst case it can be O(n^2).
Space Complexity:
The space complexity of the algorithm is dominated by the recursion stack during the QuickSelect process. In the worst case scenario, the recursion depth can be equal to the number of points n (considered highly unlikely). Hence, the space complexity in the worst case is O(n).
Applications
Navigation and Mapping: In navigation systems, identifying the closest K points to a user's location can help provide real-time recommendations for nearby restaurants, gas stations, or attractions.
Recommendation Systems: In recommendation algorithms, understanding the proximity of users to certain items or services can enhance personalized recommendations. For example, suggesting restaurants or stores that are closest to a user's preferences.
Location-Based Advertising: Advertisers can utilize the K-Closest Points to send location-based advertisements or promotions to users based on their proximity to certain stores or events.
Social Networking: In social networking apps, identifying nearby users based on their locations can facilitate friend recommendations, event invites, or networking opportunities.
Logistics and Supply Chain: In logistics and supply chain management, determining the nearest distribution centers, warehouses, or delivery points can optimize route planning and reduce transportation costs.
Emergency Services: Emergency services can use the K-Closest Points to locate the nearest hospitals, police stations, or fire departments to respond quickly to incidents.
Wireless Sensor Networks: In sensor networks, finding the K-Closest Points can be useful for aggregating data from the nearest sensors to make accurate decisions or predictions.
Data Visualization: Displaying data points on a map based on their proximity to a target point can aid in visualizing spatial relationships and patterns.
Medical Imaging: In medical imaging, identifying the K-Closest Points to a specific region of interest can help select relevant reference points for comparison or analysis.
Robotics and Autonomous Vehicles: Autonomous vehicles or robots can use the K-Closest Points to navigate and avoid obstacles, plan paths, and make informed decisions based on the environment.