K Closest points - Priority Queue / Heap / Top K

Problems
1

https://algo.monster/problems/k_closest_points

2

Please add framework .net version 6.0, so that I can execute the Priority Queue related stuff. Thanks.

1 Like
3

Thank you. We will consider .net 6.0

4

Hello,
My solution only uses heapify on the original array then uses heappop k times appending the value to the return list.
I am not using any geometry formula like it is stated in the solution, but my solution is still successful… Is my solution correct? Or are the tests incorrect?

Thanks,
Dylan

5

I’m a little confused by this alternative solution with the max heap. It says “If the new point has a smaller distance, then we pop the root of the max heap and push the new point in.” But in the code, it says:
if dist(pt) > max_heap[0][0]:
Should it be less than instead of greater than?

6

Wouldn’t using heapify on the list and returning k items in the list result in a better time complexity?

The python docs say heapify is a linear time operation.
https://docs.python.org/3/library/heapq.html#heapq.heapify

7

Note: time complexity of the alternate solution is KLog(N)

8

“is sqrt((x1 - x2)^2, (y1 - y2)^2). For distance to origin, (x2, y2) is (0, 0) so distance becomes sqrt(x1^2, y1^2).”
the formula is sqrt((x1-x2)^2 + (y1-y2)^2)

9

This is because the signs are inverted while adding to the heap, so comparison sign also changes

10

@Tulip in a heap, only the root is guaranteed to be “in sorted order” - that is, you know for sure that the root / first element is the MIN value, but the immediately following elements are not necessarily “the next minimum values” of the list. You need to heappop the list to re-heapify / sort the list to get the next minimum value.

11

It would work if you used absolute values - the test cases don’t have negative coordinates, but they’re possible.

12

How on earth am I supposed to memory imports for PriorityQueue, Comparator, implementations for the Comparator Interface and all? This is really tough to be sincere for an old man like me.

13

they use the “pythonified” notation

14

yes, but still using heapify to create the heap is more efficient, O(n), than pushing all n elements to the heap using heappush, O(nlogn)

15

It comes with time. The more you use it the less of a mystery it becomes! And you’ll remember the imports easier.

16

Change the first test case a little. Instead of the point (1, 1) change it to (1, 5). The test case will fail and then you can implement the actual correct solution (I did the same thing).

17

Easy to understand

using namespace std;

// <distance, point> 
using PointPair = pair<int, vector<int>>;

struct Compare{
    bool operator()(PointPair & a, PointPair & b) {
        return a.first > b.first;
    }
};

int distance(vector<int> point) {
    return ((point[0] * point[0]) + (point[1] * point[1]));
}

std::vector<std::vector<int>> k_closest_points(std::vector<std::vector<int>> points, int k) {
    priority_queue<PointPair, vector<PointPair>, Compare> pq;
    
    for(auto point: points) {
        pq.push(make_pair(distance(point), point));
    }
    vector<vector<int>> res;
    while(k--){
        res.push_back(pq.top().second);
        pq.pop();
    }
    return res;
}
18

Would it be cheating if I did the 1-liner in python?

return heapq.nsmallest(k, points)

19

Should be Nlog(K) actually since we keep K elements in the heap but we go through the list of coordinate N times.

20

Still waiting on .NET v 6.0.

1 Like