Statement - We have a list of points on the plane. Find the K closest points to the origin (0, 0). (Here, the distance between two points on a plane is the Euclidean distance.) You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in.)
Test Case -
Input: points = [[1,3],[-2,2]], K = 1
Output: [[-2,2]]
Question Link - Click
Code - Using Min Heap, time complexity O(nlogk).
class Solution { public: struct cmp { constexpr bool operator()( pair<double, pair<int, int>> const& a, pair<double, pair<int, int>> const& b) const noexcept { return a.first < b.first; } }; vector<vector<int>> kClosest(vector<vector<int>>& points, int K) { vector<vector<int>> ans; priority_queue<pair<double, pair<int, int>>, vector<pair<double, pair<int, int>>>, cmp> pq; for(auto p : points) { double x = double(p[0]); double y = double(p[1]); x = x*x; y = y*y; double dist = sqrt(x + y); pq.push(make_pair(dist, make_pair(p[0], p[1]))); if(pq.size() > K) { pq.pop(); } } while(!pq.empty()) { auto a = pq.top().second; pq.pop(); vector<int> v; v.push_back(a.first); v.push_back(a.second); ans.push_back(v); } return ans; } };
0 Comments