This kinda blew my mind because we want the closest k elements, which means MIN distance, but we are still using a MAX Heap. Also, correct me if I am wrong, but looks like you computing the dist() every time you compare two elements in the priority queue. You can optimize this, by computing dist() for each point only once. Anyway, this is what I came up with: class Solution { class Point implements Comparable { int x; int y; int dist; Point(int x, int y) { this.x = x; this.y = y; this.dist = (x * x) + (y * y); } public int compareTo(Point p) { return p.dist - this.dist; } } public int[][] kClosest(int[][] points, int k) { PriorityQueue pq = new PriorityQueue(); for (int[] p : points) { Point pt = new Point(p[0], p[1]); pq.add(pt); if (pq.size() > k) { pq.remove(); } } int[][] ret = new int[k][2]; int num = 0; while (!pq.isEmpty()) { Point rem = pq.remove(); ret[num][0] = rem.x; ret[num][1] = rem.y; num++; } return ret; } }
![[Java] Leetcode 1041. Robot Bounded In Circle [Array #10]](http://i.ytimg.com/vi/wUmJVRKXZCQ/mqdefault.jpg)
learned alot from this, thanks Eric!
After seeing your videos The logic becomes so easier that we don't need to see the code and we remember it.
Keep going :)
Glad to hear that
Bro you look stylish in your profile pic
best explanation, thank you !
This kinda blew my mind because we want the closest k elements, which means MIN distance, but we are still using a MAX Heap.
Also, correct me if I am wrong, but looks like you computing the dist() every time you compare two elements in the priority queue. You can optimize this, by computing dist() for each point only once.
Anyway, this is what I came up with:
class Solution {
class Point implements Comparable {
int x;
int y;
int dist;
Point(int x, int y) {
this.x = x;
this.y = y;
this.dist = (x * x) + (y * y);
}
public int compareTo(Point p) {
return p.dist - this.dist;
}
}
public int[][] kClosest(int[][] points, int k) {
PriorityQueue pq = new PriorityQueue();
for (int[] p : points) {
Point pt = new Point(p[0], p[1]);
pq.add(pt);
if (pq.size() > k) {
pq.remove();
}
}
int[][] ret = new int[k][2];
int num = 0;
while (!pq.isEmpty()) {
Point rem = pq.remove();
ret[num][0] = rem.x;
ret[num][1] = rem.y;
num++;
}
return ret;
}
}
Pair of pair vector is redundant right? We could have simply used a custom comparator in sort function
keep it up bro...solve medium and hard problems also bro.👍
I will try my best
If u have time please do a question on avl insertion and deletion sir.Atleast add to ur Queue.
I did a video in my data structure playlist call AVL Tree. Please have a look.
what is time complexcity for multimap solution
What do you mean by "Multimap"?