Hey can you please explain this Arrays.sort Function And yeah could you explain this code as well PriorityQueue maxheap=new PriorityQueue((a,b)->(b[0]*b[0]+b[1]*b[1])-(a[0]*a[0]+a[1]*a[1]));
did it in python : ) class Solution(object): def kClosest(self, points, K): d={} if len(points)==0: return for t,i in enumerate(points): d[t]=i[0]**2+i[1]**2 x=d.items() x.sort(key=lambda x:x[1]) l=[] for i in x: l.append(points[i[0]]) return l[:K]
AVL will be added but one video per day is my limit. Since I will be continuing the June challenge. It won't be possible in JUNE either. Please remind when challenges are over.
multimap is new for me. Confused in this line below. When iterator is pointing to map.begin() then how are we pushing points[it->second] ?? ans.push_back(points[it->second]);
Hey , wouldn't it be better for u as well as people who want to learn that u preferred making videos topicwise for competitive programming and for challenges like that of leetcode make a one-in-all video like errichto . Just a suggestion Awesome amount of work anyways you put in.
Then nobody will understand. I start doing what Errichto does then people who don't understand there will not understand here as well. Moreover, I am tired of making daily videos. I am just continuing coz I have committed. I prefer making 2 videos per week chosen by me. That gives me ample time to make videos on good topics.
@@techdose4u yup i know learning new concepts would help a lot like u said even if it came 2 videos per week but anyways great work , much appreciated.
I want to know one thing I am preparing for product base companies and i am not doing competitive programming instead of this i am solving problems on leetcode and i have done so many problems on GFG And yes i do belong to a tier 3 college 🙂 is this approach good? or should i start competitive programming
Submitted this solution using a custom comparator function. bool compare(vector&a, vector&b ) { int distance1 = a[0]*a[0] + a[1]*a[1]; int distance2 = b[0]*b[0] + b[1]*b[1];
I'm really sorry to give -1 for the first time on your channel. I was expecting a divide & Conquer algorithm because you solution is nowhere in the performance graph submitted by other people.
Hi tech dose yes u r right but your role is now a mentor.. And with great power comes great responsibility. People will always look after you for best solution. You have to take time to do best solution, otherwise there are lots of mentors in RUclips providing solutions. Your knowledge and way of explanation will only makes you stand out among others.
@@techdose4u If you look at leetcode performance chart, all 90%+ best performance solutions are in divide & conquer. what is your heat chart performance % in leet code chart ?
Python3:
class Solution:
def sorting_func(self, lst):
return lst[0]**2 + lst[1]**2
def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
sorted_lst = sorted(points, key= self.sorting_func)
return sorted_lst[0:K]
I waited for *quick select* algorithm :(
Dint think of applying it 😅 could have been much better since order was not important. Thanks for the suggestion.
I was expecting Quick Select too. The interviewer would not be impressed if Multi-Map was used to solve this.
After seeing your videos The logic becomes so easier that we don't need to see the code and we remember it.
Keep going :)
Nice :) then I guess I won't have to upload code 😂
@@techdose4u 😂 Of course but you have to keep others in mind too 😅
@@mansiagrawal4039 Sure :)
Simple easy one:
public int[][] kClosest(int[][] points, int K) {
Arrays.sort(points, Comparator.comparing(p -> p[0] * p[0] + p[1] * p[1]));
return Arrays.copyOfRange(points, 0, K);
}
Hey can you please explain this Arrays.sort Function And yeah could you explain this code as well PriorityQueue maxheap=new PriorityQueue((a,b)->(b[0]*b[0]+b[1]*b[1])-(a[0]*a[0]+a[1]*a[1]));
did it in python : )
class Solution(object):
def kClosest(self, points, K):
d={}
if len(points)==0:
return
for t,i in enumerate(points):
d[t]=i[0]**2+i[1]**2
x=d.items()
x.sort(key=lambda x:x[1])
l=[]
for i in x:
l.append(points[i[0]])
return l[:K]
Please upload with divide and conquer approach. Your explaination is awesome
We don't need sorting for this problem, we can solve it in O(n) using kth order statistics.
👍🏼
Hi I am a beginner please can you give some idea about the concept which you are telling
thx, love the explanation
Pair of pair vector is redundant right? We could have simply used a custom comparator in sort function
Could have taken just one pair with index value of points like I showed in multimap.
If u have time please do a question on avl insertion and deletion sir.Atleast add to ur Queue.
AVL will be added but one video per day is my limit. Since I will be continuing the June challenge. It won't be possible in JUNE either. Please remind when challenges are over.
Ok sir fine
Yes... We want red black and avl tree videos
in method 1 , 2 is misplaced in distance
multimap is new for me.
Confused in this line below. When iterator is pointing to map.begin() then how are we pushing points[it->second] ??
ans.push_back(points[it->second]);
it->second is the index of point contained in points vector as I explained in code walkthrough. I am just pushing the coordinate X,Y using the index.
@@techdose4u ok makes sense. Thank you 🙏
👍
Hey , wouldn't it be better for u as well as people who want to learn that u preferred making videos topicwise for competitive programming and for challenges like that of leetcode make a one-in-all video like errichto . Just a suggestion
Awesome amount of work anyways you put in.
Then nobody will understand. I start doing what Errichto does then people who don't understand there will not understand here as well. Moreover, I am tired of making daily videos. I am just continuing coz I have committed. I prefer making 2 videos per week chosen by me. That gives me ample time to make videos on good topics.
@@techdose4u yup i know learning new concepts would help a lot like u said even if it came 2 videos per week but anyways great work , much appreciated.
I want to know one thing
I am preparing for product base companies and i am not doing competitive programming instead of this i am solving problems on leetcode and i have done so many problems on GFG
And yes i do belong to a tier 3 college 🙂 is this approach good? or should i start competitive programming
Very good approach. No need of CP. Those who do it is either out of passion or they are following someone. Leetcode is enough to get placed.
@@techdose4u thank you so much
I am on the right path🤩
@@techdose4u thank you so much sir , you are actually helping many students with a very clear and good approach :)
DO CP!!!!
Its O(klogk + (n-k)*2logk) right? Becoz for k+1 onwards we both insert and then remove max value, n-k times
Yes right.
Submitted this solution using a custom comparator function.
bool compare(vector&a, vector&b )
{
int distance1 = a[0]*a[0] + a[1]*a[1];
int distance2 = b[0]*b[0] + b[1]*b[1];
return distance1
👍
Thank you sir!
Sir I used min-heap to solve the problem.Is it more efficient than the multimap approach?
class Point{
int x;
int y;
public:
Point(int _x, int _y){
x=_x;
y=_y;
}
int getX() const { return x; }
int getY() const { return y; }
int getDist() const { return x*x+y*y; }
};
class myComparator
{
public:
int operator() (const Point& p1, const Point& p2)
{
return p1.getDist() > p2.getDist();
}
};
class Solution {
public:
vector kClosest(vector& points, int K) {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// Creates a Min heap of points (order by distance from origin)
priority_queue min_heap;
vector result;
for(int i = 0;i
Divide and Conquer will do it in O(n)
Please share the CODE.
@@techdose4u leetcode.com/problems/k-closest-points-to-origin/solution/
In worst case it will take O(N^2).
Only average case will take O(n).
@@sakthim7160 Exactly..
Rust:
points.sort_unstable_by_key(|p| p[0].pow(2) + p[1].pow(2));
points[..k as usize].to_vec()
👍
what is time complexcity for multimap solution
O(n log N) for inserting logn in map and n is size of vector
Quick select dude.
I'm really sorry to give -1 for the first time on your channel. I was expecting a divide & Conquer algorithm because you solution is nowhere in the performance graph submitted by other people.
Heap solution is the fastest one
Divide and conquer is not fast. Did you try both the methods? How much fast solution do you expect?
Yes. I already explained how it is faster than other methods.I cannot cover each and every algo for a question, people should try them out.
Hi tech dose yes u r right but your role is now a mentor.. And with great power comes great responsibility. People will always look after you for best solution. You have to take time to do best solution, otherwise there are lots of mentors in RUclips providing solutions. Your knowledge and way of explanation will only makes you stand out among others.
@@techdose4u If you look at leetcode performance chart, all 90%+ best performance solutions are in divide & conquer. what is your heat chart performance % in leet code chart ?
bhai thanku yaar😂
Welcome
But still Heap one is better one tho
Yea