In the K Closest Point to the Origin problem, we are given n number of coordinates of a 2-D plane and we have to tell the k nearest coordinates that are closest to the origin (0,0). The closest points are those whose Euclidean distance from the origin is minimal.<\/strong><\/p>\n\n\n\n Let us understand it with an example, look at the following figure:<\/p>\n\n\n Here is the solution:<\/p>\n\n\n\n Points = [[2,3], [3,5], [-2,2]] One way to solve this problem is to find the distance of all the points from the origin and store it in a data structure, let\u2019s say, vector. We will then sort the vector to get the closest distance first. We will iterate the vector till we get k closest points. We will also store the index of the original point along with the distance so that we can reach back to the point.<\/p>\n\n\n\n The time complexity of the brute force technique is O(N log N), where N is the number of points, as we have to sort the vector which will be of size n.\u00a0The space complexity is O(N) for storing the elements in the vector.<\/p>\n\n\n\n In the max-heap approach to find K closest points to the origin, we will find the Euclidean distance of each point from the origin and store it in max-heap and maintain the size of the priority queue equal to k to store only k closest distance as size increases from k we will pop the highest distance present in the priority queue. By doing this, we will be reducing the space required from O(N) to O(k).<\/p>\n\n\n\n Euclidean distance = <\/strong>\u221a(x-0)2 <\/sup>+(y-0)2 <\/sup>Can be written as \u221a(x)2 <\/sup>+(y)2\u00a0 <\/sup>Because we are finding distance from origin<\/p>\n\n\n Here are the steps to solve this problem using max-heap:<\/p>\n\n\n\n Now, let’s move to the implementation!<\/p>\n\n\n\n Below is the C++ program to find K closest points to the origin:<\/p>\n\n\n\n Here is the Python program for this problem:<\/p>\n\n\n\n We have also Java in our arsenal:<\/p>\n\n\n\n Output:<\/strong><\/p>\n\n\n\n The time complexity of the algorithm is O(N log K), where N is the number of points and K is the value of k. This complexity arises from the insertion and extraction operations on the priority queue.<\/p>\n\n\n\n The space complexity is O(K) for storing the elements in the priority queue. As we are maintaining our priority queue for k elements only.<\/p>\n\n\n\n You can learn more about min and max heap<\/a> to better understand it.<\/p>\n\n\n\n![\"Example](\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/2-13-1024x489.png\")
<\/figure>\n<\/div>\n\n\n
K = 2
Output = [-2, 2] [2, 3]\u00a0<\/p>\n\n\n\nMax-Heap to Find K Closest Points to the Origin<\/strong><\/h2>\n\n\n\n
![\"Max-Heap](\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/1-9-1024x471.png\")
<\/figure>\n<\/div>\n\n\n\n
C++ Code<\/strong><\/h3>\n\n\n\n
#include <bits\/stdc++.h>\n\nusing namespace std;\n\nvector<vector<int>> kClosest(vector<vector<int>>& points, int k) {\n vector<vector<int>> ans;\n \n \/\/ Create a max heap (priority queue) where each element is a pair of distance and point\n priority_queue<pair<int, vector<int>>> maxHeap;\n\n \/\/ Push points onto the heap, maintaining the size at most k\n for (const auto& point : points) {\n int distance = point[0] * point[0] + point[1] * point[1];\n maxHeap.push({distance, point});\n if (maxHeap.size() > k) {\n maxHeap.pop(); \/\/ Keep the size of the heap at most k\n }\n }\n\n \/\/ Pop elements from the heap and store them in the result\n while (!maxHeap.empty()) {\n ans.push_back(maxHeap.top().second);\n maxHeap.pop();\n }\n\n \/\/ Reverse the result to get the closest points first\n reverse(ans.begin(), ans.end());\n\n return ans;\n}\n\nint main() {\n \/\/ Example usage:\n vector<vector<int>> points = {{2, 3}, {3, 5}, {-2, 2}};\n int k = 2;\n\n \/\/ Find the k closest points\n vector<vector<int>> result = kClosest(points, k);\n\n \/\/ Print the result\n cout << "The " << k << " closest points are:\\n";\n for (const auto& point : result) {\n cout << "[" << point[0] << ", " << point[1] << "] ";\n }\n\n return 0;\n}<\/pre><\/div>\n\n\n\nPython Code<\/strong><\/h3>\n\n\n\n
import heapq\n\ndef k_closest(points, k):\n ans = []\n \n # Create a max heap (priority queue) where each element is a pair of distance and point\n max_heap = []\n\n # Push points onto the heap, maintaining the size at most k\n for point in points:\n distance = point[0] ** 2 + point[1] ** 2\n heapq.heappush(max_heap, (-distance, point))\n if len(max_heap) > k:\n heapq.heappop(max_heap) # Keep the size of the heap at most k\n\n # Pop elements from the heap and store them in the result\n while max_heap:\n distance, point = heapq.heappop(max_heap)\n ans.append(point)\n\n # Reverse the result to get the closest points first\n ans.reverse()\n\n return ans\n\n# Example usage:\npoints = [[2, 3], [3, 5], [-2, 2]]\nk = 2\n\n# Find the k closest points\nresult = k_closest(points, k)\n\n# Print the result\nprint("The", k, "closest points are:")\nfor point in result:\n print(point)<\/pre><\/div>\n\n\n\nJava Code<\/strong><\/h3>\n\n\n\n
import java.util.*;\n\npublic class KClosestPoints {\n public static List<List<Integer>> kClosest(int[][] points, int k) {\n List<List<Integer>> ans = new ArrayList<>();\n \n \/\/ Create a max heap (priority queue) where each element is a pair of distance and point\n PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> Integer.compare(b[0], a[0]));\n\n \/\/ Push points onto the heap, maintaining the size at most k\n for (int[] point : points) {\n int distance = point[0] * point[0] + point[1] * point[1];\n maxHeap.offer(new int[]{distance, point[0], point[1]});\n if (maxHeap.size() > k) {\n maxHeap.poll(); \/\/ Keep the size of the heap at most k\n }\n }\n\n \/\/ Pop elements from the heap and store them in the result\n while (!maxHeap.isEmpty()) {\n int[] point = maxHeap.poll();\n ans.add(Arrays.asList(point[1], point[2]));\n }\n\n \/\/ Reverse the result to get the closest points first\n Collections.reverse(ans);\n\n return ans;\n }\n\n public static void main(String[] args) {\n \/\/ Example usage:\n int[][] points = {{2, 3}, {3, 5}, {-2, 2}};\n int k = 2;\n\n \/\/ Find the k closest points\n List<List<Integer>> result = kClosest(points, k);\n\n \/\/ Print the result\n System.out.println("The " + k + " closest points are:");\n for (List<Integer> point : result) {\n System.out.println(Arrays.toString(point.toArray()));\n }\n }\n}<\/pre><\/div>\n\n\n\nThe 2 closest points are:\n[-2, 2] [2, 3]<\/code><\/pre>\n\n\n\nConclusion <\/strong><\/h2>\n\n\n\n