I was able to solve this without watching but still watched and learnt something new that we don’t need to take square root for calculating the distance, we can directly store x^2+y^2... Thank you so much sir for making these videos 😀
Rather than storing the points(x,y) in heap, you can store the index of that point(array index) in heap, i.e. store (distance, index) in heap. This would reduce space complexity.
Wonderful explanation... i implemented in java with a slight change where i don't store key value pair in heap but only store value in heap by doing calculation in Heap Comparartor class Solution { public int[][] kClosest(int[][] points, int k) { Queue q = new PriorityQueue((p1, p2) -> Integer.compare((p2[0] * p2[0] + p2[1] * p2[1]),(p1[0] * p1[0] + p1[1] * p1[1]))); for(int i=0; i k){ q.poll(); } } int[][] arr = new int[k][2]; while(k>0){ arr[--k] = q.poll(); } return arr; } }
To use comparator in heap, the comparator should be declared as a class and the comparator function should be overloaded with operator(), but remember one thing that whenever you use comparator as a custom sorting behavior, then the heap created is min heap because only the syntax of min heap allows to use a comparator so if you want to define max heap that uses comparator, you need to reverse the output that comparator gives in order for it to work for a max heap I solved Sorting elements of an Array by Frequency using this method, leaving the code here for more insight #include using namespace std; /*IMPORTANT: comparator works in prority_queue only if they are a class which has operator() overloaded in it (got this from stackoverflow) */ class Compare { public: bool operator()(pair a, pair b) { if(a.first == b.first) return a.second > b.second; return a.first < b.first; } /*it should have been a.second < b.second and a.first > b.first because we want to arrange them in ascending order according to second element if first element (frequency) is same, but since this is ultimately creating min heap but we need max heap so i reversed the greater/lesser signs to make it a max heap*/ }; int main() { ios_base::sync_with_stdio(false); //fast I/O cin.tie(NULL); int t; cin>>t; while(t--) { int n; cin>>n; int arr[n]; unordered_map mp; //creating a max heap using custom sorting comparator priority_queue maxh; vector res; //storing frequency of elements for(int i=0; i>arr[i]; mp[arr[i]]++; } //pushing in the custom max heap as a {frequency, element} pair for(auto it=mp.begin(); it != mp.end(); it++) maxh.push({it->second, it->first}); //store in res vector from max heap while(!maxh.empty()) { int freq = maxh.top().first; int ele = maxh.top().second; while(freq--) res.push_back(ele); maxh.pop(); } for(int i=0; i
I don't think this problem is related to DP. Yet it is there in playlist of DP. Also, as mentioned in the video of Subset sum that the next problem is of Equal sum partition, but I cannot find that video in the playlist. @Aditya Verma can you clear this out?
you can take long long for distance and while storing you can do (x*1LL*x + y*1LL*y) this is just like storing (x^2+y^2) but calculation will be done in long long
10:34 hum min heap bhi to bana sakte h na .. what we will do is that we will just store the top val in some integer and the print it then return it like this we can get the closest val .............. correct me if i m wrong
sometimes x*x+y*y can overflow integer so use abs(x) + abs(y) since abs(x)*abs(x) == x*x and f(x) = x^2 ( x square) is a monotonically increasing function we will get the same order and if that also overflows since abs(x) is always non-negative we can use unsiegned integers if only 4 bytes is allowed.
Instead of storing whole pair we can just store the index of that pair. Correct me if I am wrong. import java.util.*; public class origin { public static void main(String[]args) { int dist[][] = new int[][] {{1,1} , {-2,2} , {5,8}, {0,1}}; // 2,8, int k = 2;
// max heap
PriorityQueue heap = new PriorityQueue(new Comparator() { public int compare(Pair p1, Pair p2) { return p2.getKey().compareTo(p1.getKey()); } });
int s = dist.length; // number of points given for(int i=0; i k) heap.poll(); }
int res[] = new int[k]; int i=0; while(heap.size() != 0) { res[i] = heap.poll().getValue(); i++; } for(int m=0; m
class Solution { public: vector kClosest(vector& points, int k) { priority_queue maxH; vector result; // Fix: Declare the vector properly
for (int i = 0; i < points.size(); i++) { maxH.push(make_pair(points[i][0] * points[i][0] + points[i][1] * points[i][1], make_pair(points[i][0], points[i][1]))); if (maxH.size() > k) { maxH.pop(); } } // Extract the k closest points from the priority queue while (!maxH.empty()) { result.push_back({ maxH.top().second.first, maxH.top().second.second }); maxH.pop(); } // Reverse the result vector to get the closest points first reverse(result.begin(), result.end()); return result; } };
bhai karwa sakte hain index bhi store instead of coordinates..lekin fir uske liye alag se coordinates return krne padenge uss index k... usse better ki coordinate rakho directly kehdo ki heap.top().second;...
int point[][]= { {1,3} , {-2,2} , {5,8} , {0,1}, {2,0} }; int k=3; The logic will not work for the above test case, it will give output as: (1,3) ( 2,0 ) (0,1) Whereas the expected output is : (0,1) (-2,2) and (2,0) please reply for the same onceyou identify the problem
Bro yahi output aaega tumne shyad galat approach use ki hai, Sare pairs ka square karo to 10,8,89,1,4 aaega and 89 and 10 eliminate ho jaenge so 8,1,4 bachega inke correspondence jo pairs he wahi ans he
import java.util.*; public class origin { public static void main(String[]args) { int dist[][] = new int[][] {{1,1} , {-2,2} , {5,8}, {0,1}}; // 2,8, int k = 2;
// max heap
PriorityQueue heap = new PriorityQueue(new Comparator() { public int compare(Pair p1, Pair p2) { return p2.getKey().compareTo(p1.getKey()); } });
int s = dist.length; // number of points given for(int i=0; i k) heap.poll(); }
int res[] = new int[k]; int i=0; while(heap.size() != 0) { res[i] = heap.poll().getValue(); i++; } for(int m=0; m
sol in c++ #include vector KClosestPoints(vector &points, int k) { int n =points.size(); vectorans; priority_queue< pair>pq; for (int i = 0; i k){ pq.pop(); } } while(pq.size() > 0) { ans.push_back({pq.top().second.first,pq.top().second.second}); pq.pop(); } return ans; }
JAVA soln--> class Pair{ int dist; Tuple t; Pair(int d, Tuple t1){ dist = d; t = t1; } } class Tuple{ int x; int y; Tuple(int xc, int yc){ x = xc; y = yc; } } class Com implements Comparator{ public int compare(Pair p1, Pair p2){ if(p1.dist < p2.dist){ return 1; } else if(p1.dist > p2.dist){ return -1; } else{ return 0; } } } class Solution { public int[][] kClosest(int[][] points, int k) { PriorityQueue pq = new PriorityQueue (new Com()); int row = points.length; for(int i = 0; i < row; i++){ int a = points[i][0]; int b = points[i][1]; pq.add(new Pair(((a * a) + (b * b)), new Tuple(a, b)) ); if(pq.size() > k){ pq.poll(); } } int [][] ans = new int [k][2]; int r = 0; while(pq.size() > 0){ Pair p = pq.poll(); Tuple tu = p.t; int ro = tu.x; int c = tu.y; ans[r][0] = ro; ans[r][1] = c; r++; } return ans; } }
Simple C++ Solution using customComparator: class Solution { public: struct compare { bool operator()(pair p1, pair p2) { if(p1.first == p2.first) { return p1.second.first > p2.second.first; }
return p1.first < p2.first; } }; vector kClosest(vector& points, int k) { //for closes we should use max-heap, but for this question we have choosen the min heap and have changed the compare mechanism by creating our custom comparator
class Solution { public: vector result; vectoranswer; vector kClosest(vector& points, int K) { priority_queue maxheap; for(int i=0; iK) { maxheap.pop(); } } while(maxheap.size()>0) { result.push_back(maxheap.top().second.first); result.push_back(maxheap.top().second.second); maxheap.pop(); answer.push_back(result); result.clear(); // have to empty it otherwise elements will keep on adding in the past result; } return answer; } };
The first 2 videos were so well explained that all the rest of the problems seemed so simple. Amazing explanation.
true
so true!
Yeah... I have been binging on this (and techdose heap playlist) and all these problems seem ok now
true
Damn straight
Best thing about this channel is that even the comment section of this channel teaches you a lot of new things.
I was able to solve this without watching but still watched and learnt something new that we don’t need to take square root for calculating the distance, we can directly store x^2+y^2... Thank you so much sir for making these videos 😀
Same haha
if you store sqrt it will give wrong answer
@@aayush5474 I think it'll work just fine if you store sqrt as float
relatable...
x and y in range of int but there sum of squares might lead to integer overflow
Rather than storing the points(x,y) in heap, you can store the index of that point(array index) in heap, i.e. store (distance, index) in heap. This would reduce space complexity.
Are u from Roorkee?
@@nicesacbro4891 are bhai ese kese dhundhega mansi nam ki bandi jo roorkee me rehti h , har mansi se puchega kya, facebook search marle : )
@@starc701 lmao
@@nicesacbro4891 Engineer ki tharak nhi chutegi :P
@@thisishunayn na bhai, same naam se kisiko jaanta hu, confirm kr rha tha 🤣
Could do it on my own. Always grateful for the series. Thank You.
Bhai devta h tu...
bilkulll
yes bro
sachme bhai kya padhata hai aditya bhai!
we can use {key, arr index}. array index in place of {x,y}. it will simplify our code....
Bhai tum toh Bade Heavy Driver ho ..Kya samajha ta ho🙏🙏🙏👍👍👍👏👏👏👏
actually, I have no words to describe thanks for you 🤜
Wonderful explanation... i implemented in java with a slight change where i don't store key value pair in heap but only store value in heap by doing calculation in Heap Comparartor
class Solution {
public int[][] kClosest(int[][] points, int k) {
Queue q = new PriorityQueue((p1, p2) -> Integer.compare((p2[0] * p2[0] + p2[1] * p2[1]),(p1[0] * p1[0] + p1[1] * p1[1])));
for(int i=0; i k){
q.poll();
}
}
int[][] arr = new int[k][2];
while(k>0){
arr[--k] = q.poll();
}
return arr;
}
}
awesome man.......really simple and concise code
Bhai tu awesome hai yaar. Love you brother♥️
sir please teach how to use custom comparator function in heaps 🙏🙏🙏
To use comparator in heap, the comparator should be declared as a class and the comparator function should be overloaded with operator(), but remember one thing that whenever you use comparator as a custom sorting behavior, then the heap created is min heap because only the syntax of min heap allows to use a comparator so if you want to define max heap that uses comparator, you need to reverse the output that comparator gives in order for it to work for a max heap
I solved Sorting elements of an Array by Frequency using this method, leaving the code here for more insight
#include
using namespace std;
/*IMPORTANT: comparator works in prority_queue only if they are a class which has
operator() overloaded in it (got this from stackoverflow) */
class Compare {
public:
bool operator()(pair a, pair b)
{
if(a.first == b.first)
return a.second > b.second;
return a.first < b.first;
}
/*it should have been a.second < b.second and a.first > b.first because we want to
arrange them in ascending order according to second element if first element
(frequency) is same, but since this is ultimately creating min heap but we need
max heap so i reversed the greater/lesser signs to make it a max heap*/
};
int main() {
ios_base::sync_with_stdio(false); //fast I/O
cin.tie(NULL);
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int arr[n];
unordered_map mp;
//creating a max heap using custom sorting comparator
priority_queue maxh;
vector res;
//storing frequency of elements
for(int i=0; i>arr[i];
mp[arr[i]]++;
}
//pushing in the custom max heap as a {frequency, element} pair
for(auto it=mp.begin(); it != mp.end(); it++)
maxh.push({it->second, it->first});
//store in res vector from max heap
while(!maxh.empty())
{
int freq = maxh.top().first;
int ele = maxh.top().second;
while(freq--)
res.push_back(ele);
maxh.pop();
}
for(int i=0; i
I don't think this problem is related to DP. Yet it is there in playlist of DP. Also, as mentioned in the video of Subset sum that the next problem is of Equal sum partition, but I cannot find that video in the playlist. @Aditya Verma can you clear this out?
Thank You, Buddy...Waiting for more Videos.🙌✌
instead of storing pair we can store the index of pair to reduce complexity
Thank you very much.
distance in heap will be stored in double for better precision ,as int float make some testcases fail.
No need of double if you don't take sqaure root. You may need long long int though depending on the constraints.
you can take long long for distance and while storing you can do (x*1LL*x + y*1LL*y) this is just like storing (x^2+y^2) but calculation will be done in long long
using bucket sort can be solved in O(n) tc
hamlog to dp ke playlist m the n?
This is gold series
10:34 hum min heap bhi to bana sakte h na .. what we will do is that we will just store the top val in some integer and the print it then return it like this we can get the closest val .............. correct me if i m wrong
complexity naam ki chidiya phir udd jaayegi bhai.
sometimes x*x+y*y can overflow integer so use abs(x) + abs(y) since abs(x)*abs(x) == x*x and f(x) = x^2 ( x square) is a monotonically increasing function we will get the same order and if that also overflows since abs(x) is always non-negative we can use unsiegned integers if only 4 bytes is allowed.
pretty useful thanx bro
Hi boss
I am ur junior from 2023 batch
Awesome content boss
What is the space complexity of the priority queue used here ?
nlog(k)
i guess we can also use min heap , and later on pop the elements until k is greater than K
But in that case you will have to store all the elements in the Heap, so the space complexity would be O(N) not O(K)
so the complexity would be nlog(n) rather than nlog(k).
thx bhaiya pura heaps udaya diya is sai masth explanation tha
After watching first 2 videos, i was able to solve this question without watching the video.
Thank you, dude!
Bro please continue adding problem statement from leetcode/gfg in description
Solution in cPP, According to Aditya Bhaiya :)
class Solution {
public:
vector kClosest(vector& points, int k) {
priority_queue pq;
vector res;
for(int i=0;ik){
pq.pop();
}
}
while(!(pq.empty())){
pair p=pq.top().second;
res.push_back({p.first,p.second});
pq.pop();
}
return res;
}
};
I hope it will help you.!
Amazing videos boss
Can any one tell what will be the Time complexity. Is it O(n log k) ?
Yes. Since you're traversing the array once (n) and at each point you're pushing elements into heap of size k (log k)
Nice explanation sir....
Nice explanation
You are the best👍.
bhai mast smjaa the ho
Instead of storing whole pair we can just store the index of that pair. Correct me if I am wrong.
import java.util.*;
public class origin {
public static void main(String[]args)
{
int dist[][] = new int[][] {{1,1} , {-2,2} , {5,8}, {0,1}}; // 2,8,
int k = 2;
// max heap
PriorityQueue heap = new PriorityQueue(new Comparator()
{
public int compare(Pair p1, Pair p2)
{
return p2.getKey().compareTo(p1.getKey());
}
});
int s = dist.length; // number of points given
for(int i=0; i k)
heap.poll();
}
int res[] = new int[k];
int i=0;
while(heap.size() != 0)
{
res[i] = heap.poll().getValue();
i++;
}
for(int m=0; m
that will take a extra searching time dude
Thank-you bhai ❤️
Will have to see if square falls in int range or not
yes, so to avoid this should we use pair p; as the pair definition??
thANKS SIR JI
heap k bina hi, quickselect s hogya. :)
amazon m aaya tha ye
but he is teaching heap isn't he? :-)
@@MOHDMUJTABA1 you must know other ways also
Nice explainatipn
class Solution {
public:
vector kClosest(vector& arr, int k) {
vector ans;
priority_queue< pair > pq;
for(int i=0;ik) pq.pop();
}
while(pq.size()>0)
{
ans.push_back({pq.top().second});
pq.pop();
}
return ans;
}
};
//LEETCODE 973. K Closest Points to Origin Solution
solution in C++:
class Solution {
public:
typedef pairpp;
vector kClosest(vector& points, int k) {
int n=points.size();
priority_queuepq;
for(int i=0;ik){
pq.pop();
}
}
vectorres;
while(!pq.empty()){
res.push_back({pq.top().second.first,pq.top().second.second});
pq.pop();
}
return res;
}
};
bhai mjja a rha h ds pdhne m teri vjh s
class Solution {
public:
vector kClosest(vector& points, int k) {
priority_queue maxH;
vector result; // Fix: Declare the vector properly
for (int i = 0; i < points.size(); i++) {
maxH.push(make_pair(points[i][0] * points[i][0] + points[i][1] * points[i][1], make_pair(points[i][0], points[i][1])));
if (maxH.size() > k) {
maxH.pop();
}
}
// Extract the k closest points from the priority queue
while (!maxH.empty()) {
result.push_back({ maxH.top().second.first, maxH.top().second.second });
maxH.pop();
}
// Reverse the result vector to get the closest points first
reverse(result.begin(), result.end());
return result;
}
};
awesome bro
Why don't we just store the indices instead of coordinates?
leetcode.com/problems/k-closest-points-to-origin
read this question, u'll understand.
They asked to print along with co-ordinates.
bhai karwa sakte hain index bhi store instead of coordinates..lekin fir uske liye alag se coordinates return krne padenge uss index k... usse better ki coordinate rakho directly kehdo ki heap.top().second;...
int point[][]= { {1,3} , {-2,2} , {5,8} , {0,1}, {2,0} };
int k=3;
The logic will not work for the above test case, it will give output as: (1,3) ( 2,0 ) (0,1)
Whereas the expected output is : (0,1) (-2,2) and (2,0)
please reply for the same onceyou identify the problem
Bro yahi output aaega tumne shyad galat approach use ki hai, Sare pairs ka square karo to 10,8,89,1,4 aaega and 89 and 10 eliminate ho jaenge so 8,1,4 bachega inke correspondence jo pairs he wahi ans he
GOAT !!!!!
can anyone tell ,how to take input for this problem on local IDE?
Use 2D array for input or make a custom Pair class & initiate objects of this class
Problem statement link:- leetcode.com/problems/k-closest-points-to-origin/
Someone please share their Java solution.🙁Although i understood the code but it's not working for JAVA
import java.util.*;
public class origin {
public static void main(String[]args)
{
int dist[][] = new int[][] {{1,1} , {-2,2} , {5,8}, {0,1}}; // 2,8,
int k = 2;
// max heap
PriorityQueue heap = new PriorityQueue(new Comparator()
{
public int compare(Pair p1, Pair p2)
{
return p2.getKey().compareTo(p1.getKey());
}
});
int s = dist.length; // number of points given
for(int i=0; i k)
heap.poll();
}
int res[] = new int[k];
int i=0;
while(heap.size() != 0)
{
res[i] = heap.poll().getValue();
i++;
}
for(int m=0; m
bhai problem ka code karke bhi batana please .
Another simple approach
vector kClosest(vector& points, int k) {
multimap arr; vectorans;
for(int i=0;i
LEETCODE 973 - K Closest Points to Origin
static int compare(int[] a, int[] b){
double distance1 = (a[0] * a[0]) + (a[1] * a[1]);
double distance2 = (b[0] * b[0]) + (b[1] * b[1]);
return distance1 < distance2 ? 1 : -1;
}
static int[][] kClosest(int[][] points, int k) {
//MaxHeap
PriorityQueue maxHeap = new PriorityQueue((a,b) -> compare(a,b));
for(int i = 0; i < points.length; i++){
maxHeap.add(points[i]);
if(maxHeap.size() > k){
maxHeap.remove();
}
}
int[][] result = new int[k][2];
int index = 0;
while(maxHeap.size() > 0){
result[index++] = maxHeap.remove();
}
return result;
}
Ab samaz Aaya Maths Important kyo hai zindagi me distance formulae😂😂😂
gfg problem link anyone please share🙏🙏
7:56 code it on my own
Java code
class Solution {
public int[][] kClosest(int[][] points, int k) {
PriorityQueue pq = new PriorityQueue();
for(int i = 0 ; i < points.length ;i++){
pq.add(new tuple((points[i][0]) * (points[i][0]) + (points[i][1]) * (points[i][1]) ,new pair(points[i][0] ,points[i][1])));
if(pq.size() > k){
pq.remove();
}
}
int[][] ans = new int[k][2];
int index = 0;
while(pq.size() != 0){
ans[index][0] = pq.peek().pair.a1;
ans[index][1] = pq.peek().pair.b1;
index++;
pq.remove();
}
return ans;
}
}
class pair{
int a1;
int b1;
pair(int a1 ,int b1){
this.a1 = a1;
this.b1 = b1;
}
}
class tuple implements Comparable{
int dist;
pair pair;
tuple(int dist , pair p){
this.dist = dist;
this.pair = p;
}
public int compareTo(tuple o){
return o.dist - this.dist;
}
}
lajwaaab
973. K Closest Points to Origin
class Solution {
private int squaredDistance(int[] point){
return point[0] * point[0]+point[1] * point[1];
}
public int[][] kClosest(int[][] points, int k) {
// since the question has K so we will use heap
// since closest so we will use Max heap
// save distance and index in point[] array [index , squared dist]
PriorityQueue maxHeap = new PriorityQueue((a,b)->(b[1]-a[1]));
// loop through array
int i =0;
for(int [] point: points){
int[] entry = {i++, squaredDistance(point)};
maxHeap.offer(entry);
if(maxHeap.size() > k)
maxHeap.poll();
}
int[][] result = new int[k][2];
i=0;
while(!maxHeap.isEmpty()){
result[i++]= points[maxHeap.poll()[0]];
}
return result ;
}
}
JAVA Code:
static class Pair implements Comparable {
double distance;
int[] point;
Pair(double distance, int[] point){
this.distance= distance;
this.point= point;
}
public int compareTo(Pair o) {
return Double.compare(o.distance, this.distance); // For maxHeap
}
}
public static int[][] kClosest(int[][] points, int k) {
PriorityQueue pq = new PriorityQueue();
for (int[] arr: points){
pq.offer(new Pair(Math.pow(arr[0],2 )+ Math.pow(arr[1],2) ,arr));
if (pq.size()>k){
pq.poll();
}
}
int[][] ans = new int[k][];
int index=0;
while (!pq.isEmpty()){
ans[index++]= pq.poll().point;
}
return ans;
}
sol in c++
#include
vector KClosestPoints(vector &points, int k)
{
int n =points.size();
vectorans;
priority_queue< pair>pq;
for (int i = 0; i k){
pq.pop();
}
}
while(pq.size() > 0)
{
ans.push_back({pq.top().second.first,pq.top().second.second});
pq.pop();
}
return ans;
}
LC 973 Soln.
typedef pair ppi;
class Solution {
public:
vector kClosest(vector& points, int k) {
priority_queue maxh;
vector v;
for(int i=0;ik)
maxh.pop();
}
while(maxh.size()>0)
{
v.push_back(maxh.top().second);
maxh.pop();
}
return v;
}
};
hlo bro your code is correct but when i putting sqrt() then it is not passing the every testCase ... can you tell me the problem???
🤓🤓🤓🤓🤓🤓
JAVA soln-->
class Pair{
int dist;
Tuple t;
Pair(int d, Tuple t1){
dist = d;
t = t1;
}
}
class Tuple{
int x;
int y;
Tuple(int xc, int yc){
x = xc;
y = yc;
}
}
class Com implements Comparator{
public int compare(Pair p1, Pair p2){
if(p1.dist < p2.dist){
return 1;
}
else if(p1.dist > p2.dist){
return -1;
}
else{
return 0;
}
}
}
class Solution {
public int[][] kClosest(int[][] points, int k) {
PriorityQueue pq = new PriorityQueue (new Com());
int row = points.length;
for(int i = 0; i < row; i++){
int a = points[i][0];
int b = points[i][1];
pq.add(new Pair(((a * a) + (b * b)), new Tuple(a, b)) );
if(pq.size() > k){
pq.poll();
}
}
int [][] ans = new int [k][2];
int r = 0;
while(pq.size() > 0){
Pair p = pq.poll();
Tuple tu = p.t;
int ro = tu.x;
int c = tu.y;
ans[r][0] = ro;
ans[r][1] = c;
r++;
}
return ans;
}
}
Can anyone give me the java working code
class Solution {
public int[][] kClosest(int[][] arr, int K) {
PriorityQueue maxHeap=new PriorityQueue(new Comparator() {
@Override
public int compare(Pair p1, Pair p2) {
return p2.getValue().compareTo(p1.getValue());
}
});
for (int i=0;iK)
maxHeap.poll();
}
int rst[][]=new int[maxHeap.size()][2];
int row=0;
while(maxHeap.size()!=0){
Pair p1= maxHeap.poll();
rst[row][0]=arr[p1.getKey()][0];
rst[row][1]=arr[p1.getKey()][1];
row++;
}
return rst;
}
private Integer takeSquare(int[] ints) {
return ((ints[0]*ints[0])+(ints[1]*ints[1]));
}
}
class Pair{
Integer key;
Integer value;
public Pair(Integer key, Integer value) {
this.key = key;
this.value = value;
}
public Integer getKey() {
return key;
}
public void setKey(Integer key) {
this.key = key;
}
public Integer getValue() {
return value;
}
public void setValue(Integer value) {
this.value = value;
}
}
@@VivekSharma-yl9ki kar bala so ho bhala
merci
abe kya yaar har video k comment box main merci likhta rehta hain,kuch alag likh bhai
its their codeword i think
he is not indian
@@himanshunegi5476 if he is not indian how he is understanding hindi so easily,I guess France people hardly knows hindi
@@raviashwin1157 IT"S HIS CHOICE
leetcode 973
class Solution {
public:
vector kClosest(vector& points, int k) {
priority_queue pq;
for(int i=0;ik)
pq.pop();
}
vector res;
while(!pq.empty())
{
res.push_back({pq.top().second.first, pq.top().second.second});
pq.pop();
}
return res;
}
};
Simple C++ Solution using customComparator:
class Solution {
public:
struct compare {
bool operator()(pair p1, pair p2)
{
if(p1.first == p2.first)
{
return p1.second.first > p2.second.first;
}
return p1.first < p2.first;
}
};
vector kClosest(vector& points, int k) {
//for closes we should use max-heap, but for this question we have choosen the min heap and have changed the compare mechanism by creating our custom comparator
priority_queue< pair, vector, compare>maxH;
float sum=0;
vector vec;
for(int i=0;i
not all test cases passing on interviewbit
Can someone share the code if its running smoothly in cpp?
#include
#include
using namespace std;
int main(){
priority_queue max_heap; // {(x^2+y^2),(x,y)}
int n,k;
cout > n;
int arr[n][2];
cout
class Solution {
public:
vector result;
vectoranswer;
vector kClosest(vector& points, int K) {
priority_queue maxheap;
for(int i=0; iK)
{
maxheap.pop();
}
}
while(maxheap.size()>0)
{
result.push_back(maxheap.top().second.first);
result.push_back(maxheap.top().second.second);
maxheap.pop();
answer.push_back(result);
result.clear(); // have to empty it otherwise elements will keep on adding in the past result;
}
return answer;
}
};
@@shreya-rs1fr y r u doing this inside a class?
Mayank thanks alot 🙏🙏🙏🎉🎉🎉
@@mayankgoyal8064so nice of u brother 🎉🎉🙏
class Solution {
public:
// static bool comp(pair&a, pair&b){
// return a.first < b.first;
// }
vector kClosest(vector& points, int k) {
mapmp;
for(auto x : points){
vectordata = x;
int dist = data[0]*data[0]+data[1]*data[1];
mp.insert({dist, x});
}
// vectorv(mp.begin(), mp.end());
// sort(v.begin(), v.end(), comp);
points.clear();
for(auto it : mp){
cout
class Solution {
public:
vector kClosest(vector& points, int k) {
priority_queue maxHeap;
vector ans;
for(int i=0; i k)
maxHeap.pop();
}
while(maxHeap.size() > 0)
{
ans.push_back({maxHeap.top().second.first, maxHeap.top().second.second});
maxHeap.pop();
}
return ans;
}
};
leetcode/973 :
typedef pair p;
class Solution {
public:
vector kClosest(vector& point, int k) {
vectorans;
vectordistance;
priority_queue maxh;
for(int i=0; ik){
maxh.pop();
}
}
while(maxh.size()>0){
vector vtemp=point[maxh.top().second];
ans.push_back(vtemp);
maxh.pop();
}
return ans;
}
};