Solved problem 973 : K Closest Point To Origin

racoelhosilva · racoelhosilva · commit 6ec9939b003a · 2024-02-03T09:41:13.000Z
diff --git a/Priority Queue/Medium/973_KClosestPointToOrigin.cpp b/Priority Queue/Medium/973_KClosestPointToOrigin.cpp
@@ -0,0 +1,67 @@
+/* 
+ * Problem: 973 
+ * Name: K Closest Point To Origin
+ * Difficulty: Medium
+ * Topic: Priority Queue
+ * Link: https://leetcode.com/problems/
+ */
+ 
+#include <bits/stdc++.h>
+#include <functional>
+#include <utility>
+#include <vector>
+using namespace std;
+
+//      Partial Sort Solution
+// Time Complexity: O(n log K)
+// Space Complexity: O(1)
+vector<vector<int>> kClosestPS(vector<vector<int>>& points, int K) {
+    partial_sort(points.begin(), points.begin() + K, points.end(), 
+        [](vector<int>& p, vector<int>& q) { return p[0] * p[0] + p[1] * p[1] < q[0] * q[0] + q[1] * q[1];});
+    return vector<vector<int>>(points.begin(), points.begin() + K);
+}
+
+//      Nth_Element Solution
+// Time Complexity: O(n log K)
+// Space Complexity: O(1)
+vector<vector<int>> kClosestNE(vector<vector<int>>& points, int K) {
+    nth_element(points.begin(), points.begin() + K - 1, points.end(), 
+        [](vector<int>& p, vector<int>& q) {return p[0] * p[0] + p[1] * p[1] < q[0] * q[0] + q[1] * q[1];});
+    return vector<vector<int>>(points.begin(), points.begin() + K);
+}
+
+//      Min Heap of Points
+// Time Complexity: O(n + k log n)
+// Space Complexity: O(n)
+struct MinDistanceComparator {
+    bool operator()(vector<int>& p1, vector<int>& p2){
+        return p1[0] * p1[0] + p1[1] * p1[1] > p2[0] * p2[0] + p2[1] * p2[1];
+    }
+};
+
+vector<vector<int>> kClosestPQP(vector<vector<int>>& points, int k) {
+    priority_queue<vector<int>, vector<vector<int>>, MinDistanceComparator> ordered(points.begin(), points.end());
+    vector<vector<int>> result;
+    while (k--){
+        result.push_back(ordered.top());
+        ordered.pop();
+    }
+    return result;
+}
+
+//      Min Heap of Indexes
+// Time Complexity: O(n + k log n)
+// Space Complexity: O(n)
+vector<vector<int>> kClosestPQI(vector<vector<int>>& points, int k) {
+    priority_queue<pair<double, int>, vector<pair<double,int>>, std::greater<pair<double, int>>> ordered;
+    for (int idx = 0; idx < points.size(); idx++){
+        ordered.push({points[idx][0] * points[idx][0] + points[idx][1] * points[idx][1], idx});        
+    }
+    
+    vector<vector<int>> result;
+    while (k--){
+        result.push_back(points[ordered.top().second]);
+        ordered.pop();
+    }
+    return result;
+}
diff --git a/README.md b/README.md
@@ -16,7 +16,7 @@
 
 ### Problems Solved
 
-| Total | 49 |
+| Total | 50 |
 |:---:|:---:|
 
 #### Search By Topic
@@ -36,7 +36,7 @@
 | Intervals | 2 |
 | Linked Lists | 5 |
 | Math & Geometry | 4 |
-| Priority Queue | 2 |
+| Priority Queue | 3 |
 | Sliding Window | 1 |
 | Stack | 2 |
 | Tries | 0 |
@@ -47,7 +47,7 @@
 | Difficulty | Number |
 |:---|---:|
 | Easy | 45 |
-| Medium | 4 |
+| Medium | 5 |
 | Hard | 0 |
 
 ## Milestones
