[Java] Leetcode 973. K Closest Points to Origin [Top K Elements #3]

In this video, I'm going to show you how to solve Leetcode 973. K Closest Points to Origin which is related to Top K Elements.

Here’s a quick rundown of what you’re about to learn:

⭐️ Course Contents ⭐️
⌨️ (0:00) Question
⌨️ (3:17) Solution Explain
⌨️ (5:09) Code

In the end, you’ll have a really good understanding on how to solve Leetcode 973. K Closest Points to Origin and questions that are similar to this Top K Elements.

Now, if you want to get good at Top K Elements, please checkout my Top K Elements playlist.

[דנִיאל-צק]

After seeing your videos The logic becomes so easier that we don't need to see the code and we remember it.
Keep going :)

[tommyls]

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<Point> {
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<Point> 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;
}
}

[Bjoern]

keep it up bro...solve medium and hard problems also bro.👍

[Amelia_jos]

Pair of pair vector is redundant right? We could have simply used a custom comparator in sort function

[Adolphus]

If u have time please do a question on avl insertion and deletion sir.Atleast add to ur Queue.

[TahliaYeseniaJones]

what is time complexcity for multimap solution