1 important thing to note here is why there is need to maintain the heap of pair ? We can simply push difference in heap and at the end while returning the answer we can simply subtract that value from X. But there is problem !!! as we are pushing absolute difference in heap so we cant just add the difference, there could be possibility that difference is negative. So better to have pair maintain heap using difference and its value in array as second element of pair. OR maintain heap of pair and set the bool is equal to true when difference is negative. Ans while returning add that value to X if bool is set.
We won't push abs difference, instead push the exact difference, and then use maxheap, and at the end while returning the answer we can simply add that value to X
I discovered this channel a few hours back. And have kept watching this playlist since then. You teach so well and with so much intuitiveness. Thank You.
You're the greatest teacher I've found mate, never thought I would be able to solve Leetcode medium in under 5 minutes after learning from you. Earlier, I found heaps so complicated, like CBT, then visualizing it like array, the heap order property and so on, it reached the point where I was not gonna solve any problem on it, but then I found this playlist. You're the best.
You are really amazing. Your knowledge is awesome, teaching skills superb. I didn't find anyone this cool. Please keep up with the videos , students like us will be forever in debt to your priceless videos. :)
Very nice tutorial, have gone through your Dynamic programming tutorial also ,they were amazing tutorials.Thanks brother !!!. you have great skill of competative programming.
the max heap will pop the element with greatest key . but what if there are two or more similar maximum values at the same time.the heap will pop one the items ,but it will produce different answers.
Great explanation!! but I do have a question in mind if someone can clear. What if there are duplicate elements for the keys on which we have built the max heap. In that case, on which basis the maxheap built-in module will pop the max element?
Instead of using pair we could use our own compare function instead. template class Compare { public: bool operator () (int a, int b) { return abs(k-a) < abs(k-b); } }; And then create just create the heap by priority_queue pq;
It wont work if the difference between both the keys are equal. example |1-3| = 2 & |5-3| = 2 To fix it if the keys are equal comapre the data or else compare the keys. if(p2.key == p1.key) return p2.val-p1.val; return p2.key-p1.key;
class Solution { public: vector printKClosest(vector arr, int n, int k, int x) { priority_queue maxH; // Max-heap stores (difference, element) // Push elements into the heap for (int i = 0; i k) { maxH.pop(); // Remove the farthest element if size exceeds k } } // Extract elements from the heap vector ans; while (!maxH.empty()) { ans.push_back(maxH.top().second); // Collect the elements maxH.pop(); } // Sort the result // Sort in ascending order reverse(ans.begin(),ans.end()); return ans; } };
Hey Aditya, We can also do this ques in O(log n) time using binary search by identifying the start position of the closest elements and then print k elements from that position. Can you also please explain that approach?
Correct me if am wrong we, We don't necessarily need a pair we can subtract the current element with 'X' and then add it in the max heap as we do, final we get -1 , 0 , 1 and then when we are done with the traversing we pop all and add+7 to it, ie. -1+7 = 6 , 0+7 = 7 , 1+7 = 8 , and we have found the ans.
@@thestudent1365 No, it won't be -2,-1 as you are taking the absolute value. But yes, you'll end up getting 0,1,1. And now if you add 7 to all three, then you would have 7,8,8 which is not correct. So I think you'll have to take pairs @Swapnil Padaya
@@ojasvichauhan882 Well, what you said is correct if we take the absolute of numbers while we subtract it with 7 and add them it will give the wrong answer, But if we didn't take the absolute of it and just then after doing min Heap and then adding them back up will give us the answer, Sure the order wouldn't be the same. And if one wants to keep it in the same order then what Aditya bhaiya taught us is the best and correct way, Thanks for responding.
@@swapnilpadaya163 but you can't generalize that. For eg: lets say you are calculating for n=6 instead of 7. Then according to this logic, you'll subtract 6 from every number and final heap would be like this : -1 0 1 2. So now when you'll take top 3 values and add 6 to them, ans will be 6,7,8 which is again wrong. Correct ans is 5,6,7 for this case. So basically you can not generalize this concept. You have to take absolute.
class Pair{ Integer first; Integer second; Pair(Integer first,Integer second){ this.first = first; this.second = second; } } class Solution { public List findClosestElements(int[] arr, int k, int x) { List list = new ArrayList(); PriorityQueue pq = new PriorityQueue((a, b) -> { if (a.first.equals(b.first)) { return b.second - a.second; // If distances are equal, compare values (max-heap based on values) } return b.first - a.first; // Max-heap based on distances }); for(int i=0;ik){ pq.poll(); } } while(!pq.isEmpty()){ list.add(pq.peek().second); pq.poll(); } Collections.sort(list); return list; } }
Yup.. take a language that you are comfortable with. If you are not versed with Python, do not opt for it. See.. he is using STL here for heap, if you didn't knew CPP STL well, you would try to write the heap implementation, which is unnecessary and will eat up your time.
i am unable to get how you are storing values and sorting these like 2,5 and when inserting 1,6 the stack become like 1,6 first and then 2,5 i am not getting this in all videos , could you help in this
See, what happens in pair is, first it will sort according to pair. first i.e first element but when the first elements are the same then it checks according to the second element. It is the property of the queue to do it it itself arranges after the top element.
Java code: private static void printKClosestNumbers(int[] arr, int k, int size, int x) { PriorityQueue maxHeap = new PriorityQueue(new Pair()); for (int i = 0; i < size; i++) { maxHeap.add(new Pair(Math.abs(x - arr[i]), arr[i])); if (maxHeap.size() > k) { maxHeap.poll(); } } // poll the remaining elements from the max heap. while (!maxHeap.isEmpty()) { System.out.println(maxHeap.poll().value); } }
how can we do this if x if not given directly as input? ie just find k closest elements?? like the standard dev will be lowest for those k elems in the arr
package Heap; import java.util.*; class Pair implements Comparable{ int gap; int value; public Pair(int gap, int value){ this.gap=gap; this.value= value; } @Override public int compareTo(Pair o) { if(this.value==o.value){ return 0; } else{ return this.gap-o.gap; } } } public class KClosestNumber { public static void main(String[] args) { int[] arr= {5,6,7,8,9}; int k=3; int n=7; PriorityQueue maxHeap= new PriorityQueue(3, Collections.reverseOrder()); for(int i:arr){ if(maxHeap.size()
This problem could be solved by taking a map instead of heap as well right? Map also maintains sorted order of elements. So I would make as _map_ _mpp_ and then do _mpp.insert( pair(abs( arr[i]- x ), arr[i] )_
Here is the java solution -> import java.util.*; class pairNode implements Comparable { int value; int key; pairNode(int value,int key){ this.value = value; this.key = key; } @Override public int compareTo(pairNode o) { // I'm given a link in below, check that out for compareTo and it's relation with Priority Queue return o.value > this.value ? 1 : -1; } } class Kvalue{ Queue pq = new PriorityQueue(); void Kclosest(int[] a, int k, int x){ for(int i=0;i 0){ int res = pq.peek().key; pq.poll(); System.out.println(res); } } } class test3{ public static void main(String[] args) { int[ ] a = {6, 5, 7, 8, 9}; int k = 3; int x = 7; Kvalue pq = new Kvalue(); pq.Kclosest(a,k,x); } } I find this blog about " Implementation of Priority Queue in Java " very helpful, so check this out -> www.freecodecamp.org/news/priority-queue-implementation-in-java/
hi can you explain how this is working (a,b)->(Math.abs(a-x)(a-b)); // for ascending order 2. Queue pq = new PriorityQueue((a,b)->(b-a)); // for descending order
@@ShubhamNigamdaadestroyer /* The expression (a, b) -> Math.abs(a - x) < Math.abs(b - x) ? 1 : -1 is a Java lambda expression that represents a Comparator. It compares two values a and b based on their absolute differences with a reference value x. Here's the breakdown of the expression: (a, b): This part represents the input parameters of the lambda expression. In this case, the lambda takes two parameters a and b, which are the values to be compared. Math.abs(a - x): This calculates the absolute difference between a and the reference value x. Math.abs(b - x): This calculates the absolute difference between b and the reference value x. Math.abs(a - x) < Math.abs(b - x) ? 1 : -1: This is a ternary operator that compares the absolute differences and returns 1 if the absolute difference between a and x is less than the absolute difference between b and x, and -1 otherwise. */
/* When the constructor is used with a custom Comparator, it sorts the elements in the list based on the comparison results returned by the Comparator. In the context of the lambda expression (a, b) -> Math.abs(a - x) < Math.abs(b - x) ? 1 : -1: If the expression Math.abs(a - x) < Math.abs(b - x) evaluates to true, then the value 1 is returned by the lambda expression. If the expression Math.abs(a - x) < Math.abs(b - x) evaluates to false, then the value -1 is returned by the lambda expression. Now, let's see how the constructor uses these return values: If the Comparator returns a positive value (e.g., 1): The the constructor method interprets it as an indication that the first element (a) is greater than the second element (b). So, it arranges the elements in ascending order. If the Comparator returns a negative value (e.g., -1): The the constructor method interprets it as an indication that the first element (a) is less than the second element (b). Therefore, it arranges the elements in descending order. If the Comparator returns 0: The the constructor method interprets it as an indication that both elements are equal, and their order remains unchanged. */
import java.util.Comparator; import java.util.PriorityQueue; class Pair implements Comparator { int key; int value; Pair() { } Pair(int key, int value) { this.key = key; this.value = value; } public int compare(Pair p1, Pair p2) { if (p1.value == p2.value) return 0; // no change if (p1.value < p2.value) return +1; // change the order else return -1; // no change } public String toString() { return String.valueOf(key); }
} public class pg4 { static int abs(int a, int b) { return b - a < 0 ? a - b : b - a; } public static void main(String[] args) { int[] arr = { 12, 15, 18, 2, 5, 6, 8, 11 }; int x = 15; // jis number ke nearest apne ko nikalna h k closest number PriorityQueue q = new PriorityQueue(new Pair()); int k=4; for (int i = 0; i < arr.length; i++) { q.add(new Pair(arr[i], abs(arr[i], x))); if(q.size()>k) q.poll(); } while(!q.isEmpty()) { System.out.println(q.poll()); }
package com.dss.interview.Heap; import java.util.Comparator; import java.util.PriorityQueue; class Pair implements Comparator { int key; int value; Pair() { } Pair(int key, int value) { this.key = key; this.value = value; } public int compare(Pair p1, Pair p2) { if (p1.value == p2.value) return 0; // no change if (p1.value < p2.value) return +1; // change the order else return -1; // no change } public String toString() { return String.valueOf(key); }
} public class pg4 { static int abs(int a, int b) { return b - a < 0 ? a - b : b - a; } public static void main(String[] args) { int[] arr = { 12, 15, 18, 2, 5, 6, 8, 11 }; int x = 15; // jis number ke nearest apne ko nikalna h k closest number PriorityQueue q = new PriorityQueue(new Pair()); int k=4; for (int i = 0; i < arr.length; i++) { q.add(new Pair(arr[i], abs(arr[i], x))); if(q.size()>k) q.poll(); } while(!q.isEmpty()) { System.out.println(q.poll()); }
@@subhamthakur565 so we need to write this whole pair thing in our code and then we can use pair class ?? because without class In this PriorityQueue q = new PriorityQueue(new Pair()); showing error .
package Heap; import java.util.*; class Pair implements Comparable{ int gap; int value; public Pair(int gap, int value){ this.gap=gap; this.value= value; } @Override public int compareTo(Pair o) { if(this.value==o.value){ return 0; } else{ return this.gap-o.gap; } } } public class KClosestNumber { public static void main(String[] args) { int[] arr= {5,6,7,8,9}; int k=3; int n=7; PriorityQueue maxHeap= new PriorityQueue(3, Collections.reverseOrder()); for(int i:arr){ if(maxHeap.size()
hi can you explain how this is working (a,b)->(Math.abs(a-x)(a-b)); // for ascending order 2. Queue pq = new PriorityQueue((a,b)->(b-a)); // for descending order
@@ShubhamNigamdaadestroyerTernary Operator is used here.The condition (Math.abs(a - x) < Math.abs(b - x)) checks if the absolute difference between a and x is less than the absolute difference between b and x. If the condition is true, it returns 1. If the condition is false, it returns -1
PYTHON IMPLEMENTATION !!!! import heapq from typing import List class Solution: def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]: # Max-heap to store the closest elements max_heap = []
for num in arr: # Push the negative of the absolute difference and the number itself heapq.heappush(max_heap, (-abs(num - x), -num)) if len(max_heap) > k: heapq.heappop(max_heap)
# Extract elements from the heap and store in the result list result = [] while max_heap: result.append(-heapq.heappop(max_heap)[1])
# Sort the result list before returning result.sort()
package Heap; import java.util.*; class Pair implements Comparable{ int gap; int value; public Pair(int gap, int value){ this.gap=gap; this.value= value; } @Override public int compareTo(Pair o) { if(this.value==o.value){ return 0; } else{ return this.gap-o.gap; } } } public class KClosestNumber { public static void main(String[] args) { int[] arr= {5,6,7,8,9}; int k=3; int n=7; PriorityQueue maxHeap= new PriorityQueue(3, Collections.reverseOrder()); for(int i:arr){ if(maxHeap.size()
i am unable to get this question because i am doing dsa in java , u have'nt explained anything about heaps in java, the solution in java involves lambda expression using comparable class . u are jumping directly to hard questions without explaining the basics ..
@@siddwivedi9643 thanks for the suggestion bro but i hope there was some mention about that. secondly lambda expressions is itself a bit complex to understand while using along Hashmaps and other methods . these lectures are purely c++ oriented and someone trying doing dsa in java will be definitely get confused. Apki baat se pta lg rha hai ki aapka khud ka java basics clear nhi hai.
Python Solution: from heapq import heappush, heappop, heapify def kClosestNumbers(arr,k,x): minheap = [] for i in arr: pair = [] pair.append([-abs(i-x),i]) heappush(minheap,pair) print(minheap) if len(minheap)>k: heappop(minheap) while len(minheap)>0: a = heappop(minheap) print(a[0][1], end= " ") arr = [] n = int(input("Enter the number of elements: ")) k = int(input("Enter k: ")) x = int(input("Enter x: ")) for i in range(n): arr.append(int(input())) kClosestNumbers(arr,k,x)
This is an incorrect solution in Python. If you run this code for the below input then your o/p will be [5, 2, 4, 3] which should be otherwise [1,2,3,4] arr = [1,2,3,4,5] k = 4 x = 3 Why? First understand that in Python when inserting pairs in the form of (key, value) into a heap the elements will be compared based on the keys (the first element of each pair). If two pairs have the same key, then the values (the second element of each pair) will be compared for ordering. When you run the above code your heap will look like this before popping. [(-2, 1)] [(-2, 1), (-1, 2)] [(-2, 1), (-1, 2), (0, 3)] [(-2, 1), (-1, 2), (-1, 4), (0, 3)] [(-2, 1), (-2, 5), (-1, 2),(-1, 4), (0, 3)] Note that (-2,1) came before (-2,5) because the key is the same which is -2, so now the ordering is done based on values. Based on ordering/sorting 1 comes before 5 so the heap gets the pair of (-2, 1) before (-2, 5). When you pop the topmost element from the heap the heap will look like this: [(-2, 5), (-1, 2),(-1, 4), (0, 3)] When printing the heap based on the tuple 1 value your o/p will be [5, 2, 4, 3] which is incorrect. In order to correct this code you need to check if the heap is already full (size is equal to k), check if the current element is closer to x than the top element in the heap, if so then replace the top element. Working code: from heapq import heappush, heappop def findClosestElements(arr,k,x): if len(arr) < k: return [] heap = [] for val in arr: dist = abs(val - x) if len(heap) < k: heappush(heap, (-1 * dist, val)) print(heap) else: if -1 * heap[0][0] > dist: heappop(heap) heappush(heap, (-1 * dist, val)) return sorted([val for _, val in heap]) arr = [1, 2, 3, 4, 5] k = 4 x = 3 ans = findClosestElements(arr,k,x) print(ans) Dry Run: ======= Step 1: Initialize an empty list heap to store the elements in a max-heap structure. heap = [] Step 2: Iterate over the array arr: For val = 1: a. Calculate the absolute difference dist = abs(1 - 3) = 2. b. Since the size of the heap is less than k, insert the tuple (-1 * dist, val) = (-2, 1) into the heap: heap = [(-2, 1)] For val = 2: a. Calculate the absolute difference dist = abs(2 - 3) = 1. b. Since the size of the heap is less than k, insert the tuple (-1 * dist, val) = (-1, 2) into the heap: heap = [(-2, 1), (-1, 2)] For val = 3: a. Calculate the absolute difference dist = abs(3 - 3) = 0. b. Since the size of the heap is less than k, insert the tuple (-1 * dist, val) = (0, 3) into the heap: heap = [(-2, 1), (-1, 2), (0, 3)] For val = 4: a. Calculate the absolute difference dist = abs(4 - 3) = 1. b. Since the size of the heap is less than k, insert the tuple (-1 * dist, val) = (-1, 4) into the heap: heap = [(-2, 1), (-1, 2), (0, 3), (-1, 4)] For val = 5: a. Calculate the absolute difference dist = abs(5 - 3) = 2. b. Since the size of the heap is equal to k, check if the current element is closer to x than the top element in the heap: - The top element is (-2, 1), which means the current top element's absolute difference is 2. Since dist is not less than 2, we don't replace the top element. Step 3: Extract the elements from the heap and sort them in ascending order using a list comprehension: result = sorted([val for _, val in heap]) result = [1, 2, 3, 4] The final output is [1, 2, 3, 4], which are the k=4 closest elements to x=3 in the array arr.
Everybody explains how to study DSA, but you're teaching how to actually apply and solve questions... Thanks a lott
1 important thing to note here is why there is need to maintain the heap of pair ?
We can simply push difference in heap and at the end while returning the answer we can simply subtract that value from X.
But there is problem !!!
as we are pushing absolute difference in heap so we cant just add the difference, there could be possibility that difference is negative.
So better to have pair maintain heap using difference and its value in array as second element of pair.
OR
maintain heap of pair and set the bool is equal to true when difference is negative.
Ans while returning add that value to X if bool is set.
We won't push abs difference, instead push the exact difference, and then use maxheap, and at the end while returning the answer we can simply add that value to X
Agreed !
@@souravmalik6120 nope u will get the value with max negaative value as min
and we need the closest
@@souravmalik6120 won't work for negative elements tho
I discovered this channel a few hours back. And have kept watching this playlist since then. You teach so well and with so much intuitiveness. Thank You.
you explain soo well! please make more videos on other topics as well. Even paid interview preparation courses don't teach this way
Thanks 😅
@@TheAdityaVerma men will be men
@@debasishmishra2209 i was about to write this!!!
@@sonianarendramodi2605 me too
@@debasishmishra2209 bro😂
You're the greatest teacher I've found mate, never thought I would be able to solve Leetcode medium in under 5 minutes after learning from you.
Earlier, I found heaps so complicated, like CBT, then visualizing it like array, the heap order property and so on, it reached the point where I was not gonna solve any problem on it, but then I found this playlist. You're the best.
alberto rodriguez : tu indian hi hai ?
Please make playlist of important interview questions on Hashing. Thanks a lot!!!
You are really amazing. Your knowledge is awesome, teaching skills superb. I didn't find anyone this cool. Please keep up with the videos , students like us will be forever in debt to your priceless videos. :)
Very nice tutorial, have gone through your Dynamic programming tutorial also ,they were amazing tutorials.Thanks brother !!!. you have great skill of competative programming.
the max heap will pop the element with greatest key . but what if there are two or more similar maximum values at the same time.the heap will pop one the items ,but it will produce different answers.
@@coursecollection2249 in case of duplicate, above algorithm takes that element whatever comes first. and pop the others incoming duplicate elements.
sir , please dont't stop. please make video on other topics just because of you i feel coding is easy it's too much easy
koi tension wali baat nahi hai......
until Coding Lord is here with us.
Great explanation!! but I do have a question in mind if someone can clear. What if there are duplicate elements for the keys on which we have built the max heap. In that case, on which basis the maxheap built-in module will pop the max element?
Instead of using pair we could use our own compare function instead.
template
class Compare
{
public:
bool operator () (int a, int b)
{
return abs(k-a) < abs(k-b);
}
};
And then create just create the heap by
priority_queue pq;
It's correct bro modifying a template using user defined comparator function
@@KunalKumar-ex9gm Can you please tell me why do we overload operator() instead of operator
can u please share the complete code
@@kapilsingh2816 GFG solution
class Compare
{
public:
bool operator()(pair &A, pair &B)
{
if (A.first < B.first)
{
return true;
}
else if (A.first == B.first)
{
if (A.second > B.second)
{
return true;
}
else
{
return false;
}
}
return false;
}
};
class Solution
{
public:
vector printKClosest(vector arr, int n, int k, int x)
{
priority_queue pq;
for (int i = 0; i < n; i++)
{
if (arr[i] == x)
continue;
pq.push({abs(arr[i] - x), arr[i]});
if (pq.size() > k)
{
pq.pop();
}
}
int index = k - 1;
vector res(k);
while (!pq.empty())
{
res[index] = pq.top().second;
index--;
pq.pop();
}
return res;
}
};
this man has a great depth of concept
// K Closest Numbers
import java.util.Collections;
import java.util.PriorityQueue;
class Pair implements Comparable {
int key;
int data;
Pair(int key, int data) {
this.key = key;
this.data = data;
}
@Override
public int compareTo(Pair o) {
return this.key - o.key;
}
}
public class KClosestNumbers {
public static void main(String[] args) {
int arr[] = { 5, 6, 7, 8, 9, 10 };
kClose(arr, 3, 7);
}
static void kClose(int arr[], int k, int x) {
PriorityQueue maxHeap = new PriorityQueue(Collections.reverseOrder());
for (int i : arr) {
maxHeap.add(new Pair(Math.abs(i - x), i));
if (maxHeap.size() > k) {
maxHeap.poll();
}
}
while (maxHeap.size() > 0) {
System.out.print(maxHeap.poll().data + " ");
}
}
}
Can u please explain this:
@Override
public int compareTo(pair o) {
return this.key - o.key;
}
@@ASHISH-lt1xp It is the usage of comparator in user defined class
It wont work if the difference between both the keys are equal. example |1-3| = 2 & |5-3| = 2
To fix it if the keys are equal comapre the data or else compare the keys.
if(p2.key == p1.key) return p2.val-p1.val;
return p2.key-p1.key;
4:40 -> Yes, figured it out earlier. Thanks Sir
best n simple explainations in youtube with cool tricks :)
Nice explanation sir....thanks for the playlist.....
class Solution {
public:
vector printKClosest(vector arr, int n, int k, int x) {
priority_queue maxH; // Max-heap stores (difference, element)
// Push elements into the heap
for (int i = 0; i k) {
maxH.pop(); // Remove the farthest element if size exceeds k
}
}
// Extract elements from the heap
vector ans;
while (!maxH.empty()) {
ans.push_back(maxH.top().second); // Collect the elements
maxH.pop();
}
// Sort the result
// Sort in ascending order
reverse(ans.begin(),ans.end());
return ans;
}
};
Bhai aap bohot acche se clear karte ho concepts ko. Please make videos on graph also.
Thanks for giving us such a amazing tutorial.please also make on graphs.
Hey Aditya, We can also do this ques in O(log n) time using binary search by identifying the start position of the closest elements and then print k elements from that position. Can you also please explain that approach?
If the array is sorted then we can solve in O(k/2) time only
For the general case, this method is better
Sir, can you make a playlist on hashing? It will be very helpful.
Correct me if am wrong we, We don't necessarily need a pair we can subtract the current element with 'X' and then add it in the max heap as we do, final we get -1 , 0 , 1 and then when we are done with the traversing we pop all and add+7 to it, ie. -1+7 = 6 , 0+7 = 7 , 1+7 = 8 , and we have found the ans.
i think that in this case you will get -2,-1,0 finally in the heap . so 5,6,7 will be the answer here and not 6,7,8
@@thestudent1365 No, it won't be -2,-1 as you are taking the absolute value. But yes, you'll end up getting 0,1,1. And now if you add 7 to all three, then you would have 7,8,8 which is not correct. So I think you'll have to take pairs @Swapnil Padaya
@@ojasvichauhan882 Well, what you said is correct if we take the absolute of numbers while we subtract it with 7 and add them it will give the wrong answer, But if we didn't take the absolute of it and just then after doing min Heap and then adding them back up will give us the answer, Sure the order wouldn't be the same. And if one wants to keep it in the same order then what Aditya bhaiya taught us is the best and correct way, Thanks for responding.
@@swapnilpadaya163 but you can't generalize that. For eg: lets say you are calculating for n=6 instead of 7. Then according to this logic, you'll subtract 6 from every number and final heap would be like this : -1 0 1 2. So now when you'll take top 3 values and add 6 to them, ans will be 6,7,8 which is again wrong. Correct ans is 5,6,7 for this case. So basically you can not generalize this concept. You have to take absolute.
@@swapnilpadaya163 can u help me with the python code I m stuck
Great Explanation! Thanks a Ton!!
BHAI TUM BHUT ACHA PADHETEY HO DIL GARDEN GARDEN HO GYA SAMJH KE
Thank you soo much. You really teach very nice.
Keep on making such video😊
practice problem link : leetcode.com/problems/find-k-closest-elements/
thanks
Nice explanation!!
Very well explained
Aag 🔥🔥🔥🔥🔥🔥🔥
Thanks brother, Do subscribe and share.
Lo bhai... heap mein aag laga diya tumne.
Your video is superb😊😊
Thank you very much.
class Pair{
Integer first;
Integer second;
Pair(Integer first,Integer second){
this.first = first;
this.second = second;
}
}
class Solution {
public List findClosestElements(int[] arr, int k, int x) {
List list = new ArrayList();
PriorityQueue pq = new PriorityQueue((a, b) -> {
if (a.first.equals(b.first)) {
return b.second - a.second; // If distances are equal, compare values (max-heap based on values)
}
return b.first - a.first; // Max-heap based on distances
});
for(int i=0;ik){
pq.poll();
}
}
while(!pq.isEmpty()){
list.add(pq.peek().second);
pq.poll();
}
Collections.sort(list);
return list;
}
}
is their any advice you have on choosing lang for interview questions?
is there any reason to not use python since its easiest?
for interview you can choose any lang but you shud be well versed with it (from my interview exp)
Yup.. take a language that you are comfortable with. If you are not versed with Python, do not opt for it.
See.. he is using STL here for heap, if you didn't knew CPP STL well, you would try to write the heap implementation, which is unnecessary and will eat up your time.
i am unable to get how you are storing values and sorting these like 2,5 and when inserting 1,6 the stack become like 1,6 first and then 2,5 i am not getting this in all videos , could you help in this
See, what happens in pair is, first it will sort according to pair. first i.e first element but when the first elements are the same then it checks according to the second element. It is the property of the queue to do it
it itself arranges after the top element.
@@shreya-rs1fr thnku ,the same thing I was searching for
Java code:
private static void printKClosestNumbers(int[] arr, int k, int size, int x) {
PriorityQueue maxHeap = new PriorityQueue(new Pair());
for (int i = 0; i < size; i++) {
maxHeap.add(new Pair(Math.abs(x - arr[i]), arr[i]));
if (maxHeap.size() > k) {
maxHeap.poll();
}
}
// poll the remaining elements from the max heap.
while (!maxHeap.isEmpty()) {
System.out.println(maxHeap.poll().value);
}
}
but there is no predefined pair class in java ..?
in java priority queue insert in logn , as we inserting n time complexity is nlog(n)?
What if two pairs have same absolute difference and we want to pop the pair with greater arr[i]???
I also have the same doubt
Since, we are given a sorted array.....so can't we apply binary search to reduce the complexity?
It's not sorted always.
what will be the changes if i want output in order like first closest should come first ....so on
can we make our comparator and sort priority_queue according to that and apply logic of k largest or smallest element
par iska complexity 0(n) ho jayega + heap ka O(n log n).
Great video boss 👍 👏 👌
THANK YOU !!!!!
how can we do this if x if not given directly as input?
ie just find k closest elements??
like the standard dev will be lowest for those k elems in the arr
Why complicate ? Why not just use something like `var maxHeap = new PriorityQueue(k, (a, b) -> Math.abs(x - b) - Math.abs(x - a))` ?
your explanation is great. please solve this question in java
package Heap;
import java.util.*;
class Pair implements Comparable{
int gap;
int value;
public Pair(int gap, int value){
this.gap=gap;
this.value= value;
}
@Override
public int compareTo(Pair o) {
if(this.value==o.value){
return 0;
}
else{
return this.gap-o.gap;
}
}
}
public class KClosestNumber {
public static void main(String[] args) {
int[] arr= {5,6,7,8,9};
int k=3;
int n=7;
PriorityQueue maxHeap= new PriorityQueue(3, Collections.reverseOrder());
for(int i:arr){
if(maxHeap.size()
Do heap of pair element take first element of q to compare ?
Thanks a lot sir😍😍😍😍😍😍😍😍😍😍
bhadiya question!!
@Aditya verma please make video on other topics as soon as possible
u r the best pls or videos bnaaiye
what is i make size of heap before itself then what will happen if it insert element will it pop useless element by itself
My leetcode 658 java solution :
class Solution {
public List findClosestElements(int[] arr, int k, int x) {
PriorityQueue pq = new PriorityQueue(arr.length,(o1,o2)->
{
if(Math.abs(o1-x)==Math.abs(o2-x))
{
if(o1>o2) return -1;
return 1;
}
else if(Math.abs(o1-x)>Math.abs(o2-x)) return -1;
else return 1;
});
for(int n:arr)
{
pq.add(n);
if(pq.size()>k) pq.remove();
}
List result = new ArrayList();
while(pq.size()>0) result.add(pq.remove());
Collections.sort(result);
return result;
}
}
This problem could be solved by taking a map instead of heap as well right?
Map also maintains sorted order of elements. So I would make as _map_ _mpp_ and then do _mpp.insert( pair(abs( arr[i]- x ), arr[i] )_
time complexity of sort in map in nlogn but in heap it's nlogk which is far far better
How can I implement pairHeap in JAVA? Can anyone help me with example?
you can create a class for that
Can't we use tree map instead of this..
Here is the java solution ->
import java.util.*;
class pairNode implements Comparable {
int value;
int key;
pairNode(int value,int key){
this.value = value;
this.key = key;
}
@Override
public int compareTo(pairNode o) {
// I'm given a link in below, check that out for compareTo and it's relation with Priority Queue
return o.value > this.value ? 1 : -1;
}
}
class Kvalue{
Queue pq = new PriorityQueue();
void Kclosest(int[] a, int k, int x){
for(int i=0;i 0){
int res = pq.peek().key;
pq.poll();
System.out.println(res);
}
}
}
class test3{
public static void main(String[] args) {
int[ ] a = {6, 5, 7, 8, 9};
int k = 3;
int x = 7;
Kvalue pq = new Kvalue();
pq.Kclosest(a,k,x);
}
}
I find this blog about " Implementation of Priority Queue in Java " very helpful, so check this out ->
www.freecodecamp.org/news/priority-queue-implementation-in-java/
@@devplus7131 just keep the link and not the solution, this will make people not work. Though I appreciate your efforts to share the link
Legendary Aditya Verma
can u make a series on hash map
Leetcode 658 Java Solution:
class Solution {
public List findClosestElements(int[] arr, int k, int x) {
Queue pq = new PriorityQueue((a,b)->(Math.abs(a-x)k)
pq.remove();
}
while(!pq.isEmpty()) {
result.add(pq.remove());
}
Collections.sort(result);
return result;
}
}
hi can you explain how this is working (a,b)->(Math.abs(a-x)(a-b)); // for ascending order
2. Queue pq = new PriorityQueue((a,b)->(b-a)); // for descending order
@@ShubhamNigamdaadestroyer
/*
The expression (a, b) -> Math.abs(a - x) < Math.abs(b - x) ? 1 : -1 is a Java lambda expression that represents a Comparator. It compares two values a and b based on their absolute differences with a reference value x.
Here's the breakdown of the expression:
(a, b): This part represents the input parameters of the lambda expression. In this case, the lambda takes two parameters a and b, which are the values to be compared.
Math.abs(a - x): This calculates the absolute difference between a and the reference value x.
Math.abs(b - x): This calculates the absolute difference between b and the reference value x.
Math.abs(a - x) < Math.abs(b - x) ? 1 : -1: This is a ternary operator that compares the absolute differences and returns 1 if the absolute difference between a and x is less than the absolute difference between b and x, and -1 otherwise.
*/
/*
When the constructor is used with a custom Comparator, it sorts the elements in the list based on the comparison results returned by the Comparator.
In the context of the lambda expression (a, b) -> Math.abs(a - x) < Math.abs(b - x) ? 1 : -1:
If the expression Math.abs(a - x) < Math.abs(b - x) evaluates to true, then the value 1 is returned by the lambda expression.
If the expression Math.abs(a - x) < Math.abs(b - x) evaluates to false, then the value -1 is returned by the lambda expression.
Now, let's see how the constructor uses these return values:
If the Comparator returns a positive value (e.g., 1):
The the constructor method interprets it as an indication that the first element (a) is greater than the second element (b). So, it arranges the elements in ascending order.
If the Comparator returns a negative value (e.g., -1):
The the constructor method interprets it as an indication that the first element (a) is less than the second element (b). Therefore, it arranges the elements in descending order.
If the Comparator returns 0:
The the constructor method interprets it as an indication that both elements are equal, and their order remains unchanged.
*/
Finally channel is monetized
2 rs ki Pepsi
Bhai apna sexy
@Zexy Turpa $ 1000 ki pepsi Bhai apna SEXY
i have not been able to find a great explanation of this question online. finally, when i did, it was in C. please tell me the solution in java
instead of pair we can try array of size 2
Thanks a lot sir
@Aditya Can you explain the same problem with binary search?
What is the TC?
it will work only for O(nlogk) so dont worry
OP bro👏👏
Ek value hi rakho ...7 add karke output dikha do ...ye bhi to possible h
thanks a lot
what is time complexity?
If we have to do in logn and 0(1) space then
binary search
find the position of x then ( position-k )and (position+k ) contains our answer
Is this a binary search problem
Can we insert a pair of values inside heap in java ? If any one know please reply.
i also have same question
well using treemap we can implement it in java
import java.util.Comparator;
import java.util.PriorityQueue;
class Pair implements Comparator {
int key;
int value;
Pair() {
}
Pair(int key, int value) {
this.key = key;
this.value = value;
}
public int compare(Pair p1, Pair p2) {
if (p1.value == p2.value)
return 0; // no change
if (p1.value < p2.value)
return +1; // change the order
else
return -1; // no change
}
public String toString()
{
return String.valueOf(key);
}
}
public class pg4 {
static int abs(int a, int b) {
return b - a < 0 ? a - b : b - a;
}
public static void main(String[] args) {
int[] arr = { 12, 15, 18, 2, 5, 6, 8, 11 };
int x = 15; // jis number ke nearest apne ko nikalna h k closest number
PriorityQueue q = new PriorityQueue(new Pair());
int k=4;
for (int i = 0; i < arr.length; i++)
{
q.add(new Pair(arr[i], abs(arr[i], x)));
if(q.size()>k)
q.poll();
}
while(!q.isEmpty())
{
System.out.println(q.poll());
}
}
}
// output
11
12
18
15
@@subhamthakur565 bro can u help me with python code for this problem...I m stuck
@@AmitKumar-hq4wb Did u get the python code ? or you still need it
can anyone explain a good way to do this in python? since we cant really push a tuple in heap in python that i am aware of.
NO we can push a tuple I python heapq library.. for e.g "heapq.heappush(li,(4,100))"
Why You Need to push a tuple you can push a list also.
java mai pair kaise banate hai??
package com.dss.interview.Heap;
import java.util.Comparator;
import java.util.PriorityQueue;
class Pair implements Comparator {
int key;
int value;
Pair() {
}
Pair(int key, int value) {
this.key = key;
this.value = value;
}
public int compare(Pair p1, Pair p2) {
if (p1.value == p2.value)
return 0; // no change
if (p1.value < p2.value)
return +1; // change the order
else
return -1; // no change
}
public String toString()
{
return String.valueOf(key);
}
}
public class pg4 {
static int abs(int a, int b) {
return b - a < 0 ? a - b : b - a;
}
public static void main(String[] args) {
int[] arr = { 12, 15, 18, 2, 5, 6, 8, 11 };
int x = 15; // jis number ke nearest apne ko nikalna h k closest number
PriorityQueue q = new PriorityQueue(new Pair());
int k=4;
for (int i = 0; i < arr.length; i++)
{
q.add(new Pair(arr[i], abs(arr[i], x)));
if(q.size()>k)
q.poll();
}
while(!q.isEmpty())
{
System.out.println(q.poll());
}
}
}
@@subhamthakur565 so we need to write this whole pair thing in our code and then we can use pair class ??
because without class In this
PriorityQueue q = new PriorityQueue(new Pair());
showing error .
Gajab bhai
Please provide a solution in java aswell
package Heap;
import java.util.*;
class Pair implements Comparable{
int gap;
int value;
public Pair(int gap, int value){
this.gap=gap;
this.value= value;
}
@Override
public int compareTo(Pair o) {
if(this.value==o.value){
return 0;
}
else{
return this.gap-o.gap;
}
}
}
public class KClosestNumber {
public static void main(String[] args) {
int[] arr= {5,6,7,8,9};
int k=3;
int n=7;
PriorityQueue maxHeap= new PriorityQueue(3, Collections.reverseOrder());
for(int i:arr){
if(maxHeap.size()
merci
can someone give the ques link?
how we can solve this particular problem using python
Simple Java Solution-
private static void KClosestElements(int[] arr, int k, int x) {
PriorityQueue pq = new PriorityQueue((a, b) -> Math.abs(b-x) - Math.abs(a -x)); //max-heap
for (int i : arr) {
pq.add(i);
if (pq.size() > k) {
pq.poll();
}
}
while (pq.size() > 0) {
System.out.print(pq.poll() + " ");
}
}
Bro yeh max heap kaise bnai apne ...plz btana....maths.abs sai confusion ho rha hai...plz reply
@@developer-cminiclip8745 Math.abs will make sure the positive value.. It will do b-x and if it results negative.. Abs will make it positive
hi can you explain how this is working (a,b)->(Math.abs(a-x)(a-b)); // for ascending order
2. Queue pq = new PriorityQueue((a,b)->(b-a)); // for descending order
@@ShubhamNigamdaadestroyerTernary Operator is used here.The condition (Math.abs(a - x) < Math.abs(b - x)) checks if the absolute difference between a and x is less than the absolute difference between b and x.
If the condition is true, it returns 1.
If the condition is false, it returns -1
first pair will be sorted automatically
how to create a pairing heap in python plz help
push as a tuple, it will build the heap based on the first element
PYTHON IMPLEMENTATION !!!!
import heapq
from typing import List
class Solution:
def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
# Max-heap to store the closest elements
max_heap = []
for num in arr:
# Push the negative of the absolute difference and the number itself
heapq.heappush(max_heap, (-abs(num - x), -num))
if len(max_heap) > k:
heapq.heappop(max_heap)
# Extract elements from the heap and store in the result list
result = []
while max_heap:
result.append(-heapq.heappop(max_heap)[1])
# Sort the result list before returning
result.sort()
return result
can someone plaese tell me how to use pair in java.
or provide the complete code in java.
import java.util.*;
class Pair implements Comparable
{
int key;
int data;
Pair(int key, int data)
{
this.key = key;
this.data = data;
}
public int compareTo(Pair o)
{
return this.key - o.key;
}
}
public class K_closest_nos
{
static void solve(int arr[], int k, int x)
{
PriorityQueue pq = new PriorityQueue(Collections.reverseOrder());
for (int i : arr)
{
pq.add(new Pair(Math.abs(i - x), i));
if (pq.size() > k)
pq.poll();
}
while (pq.size() > 0)
System.out.print(pq.poll().data + " ");
}
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int arr[]=new int[n];
for(int x=0;x
how to do this pair thing in heap in python..pls help anyone!!
can anyone give me the c++ code
graphhhhhh
someone please paste java code wasted an hour still cant figure out
hats down
Please tell the syntax of Paired PriorityQueue in Java
package Heap;
import java.util.*;
class Pair implements Comparable{
int gap;
int value;
public Pair(int gap, int value){
this.gap=gap;
this.value= value;
}
@Override
public int compareTo(Pair o) {
if(this.value==o.value){
return 0;
}
else{
return this.gap-o.gap;
}
}
}
public class KClosestNumber {
public static void main(String[] args) {
int[] arr= {5,6,7,8,9};
int k=3;
int n=7;
PriorityQueue maxHeap= new PriorityQueue(3, Collections.reverseOrder());
for(int i:arr){
if(maxHeap.size()
@@rajitsrajan2644 Bro abb toh placement bhi ho gyi... thanks btw 😀
Maybe it will come handy in next interview😅😝
i am unable to get this question because i am doing dsa in java , u have'nt explained anything about heaps in java,
the solution in java involves lambda expression using comparable class . u are jumping directly to hard questions without explaining the basics ..
bhaii java me pair ki class banani pdegi , aur class banana java me basic cheez hai ...Phle basics clear kro !!
@@siddwivedi9643 thanks for the suggestion bro but i hope there was some mention about that. secondly lambda expressions is itself a bit complex to understand while using along Hashmaps and other methods . these lectures are purely c++ oriented and someone trying doing dsa in java will be definitely get confused. Apki baat se pta lg rha hai ki aapka khud ka java basics clear nhi hai.
op exlanation
first like then i watch the video..
java solution:
class Solution {
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;
}
}
int[] printKClosest(int[] arr, int n, int k, int x)
{
int ans[]=new int[k];
PriorityQueue pq = new PriorityQueue(
new Comparator()
{
public int compare(Pair p1, Pair p2)
{
return p2.getValue().compareTo(
p1.getValue());
}
});
for(int i=0;ik)
{
pq.poll();
}
}
}
int j=k-1;
while(pq.size()>0)
{
ans[j]=pq.peek().getKey();
pq.poll();
j--;
}
return ans;
}
}
bhai isi ke company mein aane ke liye!!
guru ji bit pe videos bana do
Python Solution:
from heapq import heappush, heappop, heapify
def kClosestNumbers(arr,k,x):
minheap = []
for i in arr:
pair = []
pair.append([-abs(i-x),i])
heappush(minheap,pair)
print(minheap)
if len(minheap)>k:
heappop(minheap)
while len(minheap)>0:
a = heappop(minheap)
print(a[0][1], end= " ")
arr = []
n = int(input("Enter the number of elements: "))
k = int(input("Enter k: "))
x = int(input("Enter x: "))
for i in range(n):
arr.append(int(input()))
kClosestNumbers(arr,k,x)
This is an incorrect solution in Python.
If you run this code for the below input then your o/p will be [5, 2, 4, 3] which should be otherwise [1,2,3,4]
arr = [1,2,3,4,5]
k = 4
x = 3
Why? First understand that in Python when inserting pairs in the form of (key, value) into a heap the elements will be compared based on the keys (the first element of each pair). If two pairs have the same key, then the values (the second element of each pair) will be compared for ordering. When you run the above code your heap will look like this before popping.
[(-2, 1)]
[(-2, 1), (-1, 2)]
[(-2, 1), (-1, 2), (0, 3)]
[(-2, 1), (-1, 2), (-1, 4), (0, 3)]
[(-2, 1), (-2, 5), (-1, 2),(-1, 4), (0, 3)]
Note that (-2,1) came before (-2,5) because the key is the same which is -2, so now the ordering is done based on values. Based
on ordering/sorting 1 comes before 5 so the heap gets the pair of (-2, 1) before (-2, 5).
When you pop the topmost element from the heap the heap will look like this:
[(-2, 5), (-1, 2),(-1, 4), (0, 3)]
When printing the heap based on the tuple 1 value your o/p will be [5, 2, 4, 3] which is incorrect.
In order to correct this code you need to check if the heap is already full (size is equal to k), check if the current element is closer to x than the top element in the heap, if so then replace the top element.
Working code:
from heapq import heappush, heappop
def findClosestElements(arr,k,x):
if len(arr) < k:
return []
heap = []
for val in arr:
dist = abs(val - x)
if len(heap) < k:
heappush(heap, (-1 * dist, val))
print(heap)
else:
if -1 * heap[0][0] > dist:
heappop(heap)
heappush(heap, (-1 * dist, val))
return sorted([val for _, val in heap])
arr = [1, 2, 3, 4, 5]
k = 4
x = 3
ans = findClosestElements(arr,k,x)
print(ans)
Dry Run:
=======
Step 1: Initialize an empty list heap to store the elements in a max-heap structure.
heap = []
Step 2: Iterate over the array arr:
For val = 1:
a. Calculate the absolute difference dist = abs(1 - 3) = 2.
b. Since the size of the heap is less than k, insert the tuple (-1 * dist, val) = (-2, 1) into the heap:
heap = [(-2, 1)]
For val = 2:
a. Calculate the absolute difference dist = abs(2 - 3) = 1.
b. Since the size of the heap is less than k, insert the tuple (-1 * dist, val) = (-1, 2) into the heap:
heap = [(-2, 1), (-1, 2)]
For val = 3:
a. Calculate the absolute difference dist = abs(3 - 3) = 0.
b. Since the size of the heap is less than k, insert the tuple (-1 * dist, val) = (0, 3) into the heap:
heap = [(-2, 1), (-1, 2), (0, 3)]
For val = 4:
a. Calculate the absolute difference dist = abs(4 - 3) = 1.
b. Since the size of the heap is less than k, insert the tuple (-1 * dist, val) = (-1, 4) into the heap:
heap = [(-2, 1), (-1, 2), (0, 3), (-1, 4)]
For val = 5:
a. Calculate the absolute difference dist = abs(5 - 3) = 2.
b. Since the size of the heap is equal to k, check if the current element is closer to x than the top element in the heap:
- The top element is (-2, 1), which means the current top element's absolute difference is 2. Since dist is not less than 2, we don't replace the top element.
Step 3: Extract the elements from the heap and sort them in ascending order using a list comprehension:
result = sorted([val for _, val in heap])
result = [1, 2, 3, 4]
The final output is [1, 2, 3, 4], which are the k=4 closest elements to x=3 in the array arr.