5 K Closest Numbers

แชร์
ฝัง
  • เผยแพร่เมื่อ 24 ธ.ค. 2024

ความคิดเห็น • 224

  • @tanboyy08
    @tanboyy08 4 ปีที่แล้ว +44

    Everybody explains how to study DSA, but you're teaching how to actually apply and solve questions... Thanks a lott

  • @Pratik-Kedar
    @Pratik-Kedar 4 ปีที่แล้ว +116

    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.

    • @souravmalik6120
      @souravmalik6120 2 ปีที่แล้ว +4

      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

    • @malkeetsapien4852
      @malkeetsapien4852 2 ปีที่แล้ว +2

      Agreed !

    • @ranudrolia
      @ranudrolia 2 ปีที่แล้ว +6

      @@souravmalik6120 nope u will get the value with max negaative value as min
      and we need the closest

    • @AdityaKumar-y7g7k
      @AdityaKumar-y7g7k 8 หลายเดือนก่อน

      @@souravmalik6120 won't work for negative elements tho

  • @mohitzen
    @mohitzen 11 หลายเดือนก่อน +1

    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.

  • @manishakhanchandani5618
    @manishakhanchandani5618 4 ปีที่แล้ว +92

    you explain soo well! please make more videos on other topics as well. Even paid interview preparation courses don't teach this way

  • @AlbertoRodriguez-oe6jo
    @AlbertoRodriguez-oe6jo 3 ปีที่แล้ว +11

    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.

    • @AdityaSingh-ql9ke
      @AdityaSingh-ql9ke 2 ปีที่แล้ว +3

      alberto rodriguez : tu indian hi hai ?

  • @vikashkumarchaurasia1299
    @vikashkumarchaurasia1299 4 ปีที่แล้ว +73

    Please make playlist of important interview questions on Hashing. Thanks a lot!!!

  • @manjushajagtap3718
    @manjushajagtap3718 4 ปีที่แล้ว +8

    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. :)

  • @vikashkumarchaurasia1299
    @vikashkumarchaurasia1299 4 ปีที่แล้ว +20

    Very nice tutorial, have gone through your Dynamic programming tutorial also ,they were amazing tutorials.Thanks brother !!!. you have great skill of competative programming.

  • @shashwatmishra6821
    @shashwatmishra6821 4 ปีที่แล้ว +17

    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.

    • @naveenshah8032
      @naveenshah8032 3 ปีที่แล้ว +2

      @@coursecollection2249 in case of duplicate, above algorithm takes that element whatever comes first. and pop the others incoming duplicate elements.

  • @ytsh5752
    @ytsh5752 2 ปีที่แล้ว +1

    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

  • @AnkushKumar-mk8ns
    @AnkushKumar-mk8ns 4 ปีที่แล้ว +7

    koi tension wali baat nahi hai......
    until Coding Lord is here with us.

  • @shiwangisharma5504
    @shiwangisharma5504 3 ปีที่แล้ว +7

    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?

  • @AkhilNairjedi18
    @AkhilNairjedi18 4 ปีที่แล้ว +23

    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;

    • @KunalKumar-ex9gm
      @KunalKumar-ex9gm 4 ปีที่แล้ว +1

      It's correct bro modifying a template using user defined comparator function

    • @_N_E_E_R_A_J_
      @_N_E_E_R_A_J_ 2 ปีที่แล้ว +1

      @@KunalKumar-ex9gm Can you please tell me why do we overload operator() instead of operator

    • @kapilsingh2816
      @kapilsingh2816 ปีที่แล้ว

      can u please share the complete code

    • @rishabhgupta9846
      @rishabhgupta9846 ปีที่แล้ว

      @@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;
      }
      };

  • @harendrameghwal1374
    @harendrameghwal1374 3 ปีที่แล้ว +2

    this man has a great depth of concept

  • @BikkiMahato
    @BikkiMahato 4 ปีที่แล้ว +22

    // 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 + " ");
    }
    }
    }

    • @ASHISH-lt1xp
      @ASHISH-lt1xp 2 ปีที่แล้ว +1

      Can u please explain this:
      @Override
      public int compareTo(pair o) {
      return this.key - o.key;
      }

    • @chitranshsrivastava5880
      @chitranshsrivastava5880 2 ปีที่แล้ว

      @@ASHISH-lt1xp It is the usage of comparator in user defined class

    • @maheshwarang4000
      @maheshwarang4000 ปีที่แล้ว

      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;

  • @imPriyansh77
    @imPriyansh77 9 หลายเดือนก่อน

    4:40 -> Yes, figured it out earlier. Thanks Sir

  • @UJJWALGIRIRA
    @UJJWALGIRIRA 3 ปีที่แล้ว

    best n simple explainations in youtube with cool tricks :)

  • @paragroy5359
    @paragroy5359 4 ปีที่แล้ว +2

    Nice explanation sir....thanks for the playlist.....

  • @JigsawXop
    @JigsawXop 9 วันที่ผ่านมา +1

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

  • @ashutoshkhandelwal2837
    @ashutoshkhandelwal2837 4 ปีที่แล้ว

    Bhai aap bohot acche se clear karte ho concepts ko. Please make videos on graph also.

  • @dikshabharti6516
    @dikshabharti6516 3 ปีที่แล้ว +2

    Thanks for giving us such a amazing tutorial.please also make on graphs.

  • @heenaagarwal6795
    @heenaagarwal6795 4 ปีที่แล้ว +7

    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?

    • @hassanimam6472
      @hassanimam6472 4 ปีที่แล้ว +11

      If the array is sorted then we can solve in O(k/2) time only
      For the general case, this method is better

  • @indrajitkabiraj5401
    @indrajitkabiraj5401 4 ปีที่แล้ว +4

    Sir, can you make a playlist on hashing? It will be very helpful.

  • @swapnilpadaya163
    @swapnilpadaya163 4 ปีที่แล้ว +3

    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
      @thestudent1365 4 ปีที่แล้ว +1

      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

    • @ojasvichauhan882
      @ojasvichauhan882 4 ปีที่แล้ว +1

      @@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

    • @swapnilpadaya163
      @swapnilpadaya163 4 ปีที่แล้ว

      @@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.

    • @ojasvichauhan882
      @ojasvichauhan882 4 ปีที่แล้ว

      @@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.

    • @AmitKumar-hq4wb
      @AmitKumar-hq4wb 4 ปีที่แล้ว

      @@swapnilpadaya163 can u help me with the python code I m stuck

  • @palakmanocha6509
    @palakmanocha6509 4 ปีที่แล้ว +1

    Great Explanation! Thanks a Ton!!

  • @remedyiq8034
    @remedyiq8034 2 ปีที่แล้ว

    BHAI TUM BHUT ACHA PADHETEY HO DIL GARDEN GARDEN HO GYA SAMJH KE

  • @StoriesChangedLife
    @StoriesChangedLife ปีที่แล้ว

    Thank you soo much. You really teach very nice.

  • @tridevthakur5397
    @tridevthakur5397 4 ปีที่แล้ว +1

    Keep on making such video😊

  • @jainuinely_confused
    @jainuinely_confused 4 ปีที่แล้ว +9

    practice problem link : leetcode.com/problems/find-k-closest-elements/

  • @codetochange8
    @codetochange8 2 ปีที่แล้ว

    Nice explanation!!

  • @VedPrakashLearnToGrow
    @VedPrakashLearnToGrow 3 ปีที่แล้ว +1

    Very well explained

  • @nishanksoni7120
    @nishanksoni7120 4 ปีที่แล้ว +22

    Aag 🔥🔥🔥🔥🔥🔥🔥

    • @TheAdityaVerma
      @TheAdityaVerma  4 ปีที่แล้ว +4

      Thanks brother, Do subscribe and share.

    • @PabitraPadhy
      @PabitraPadhy 3 ปีที่แล้ว +1

      Lo bhai... heap mein aag laga diya tumne.

  • @tridevthakur5397
    @tridevthakur5397 4 ปีที่แล้ว

    Your video is superb😊😊

  • @vakhariyajay315
    @vakhariyajay315 ปีที่แล้ว

    Thank you very much.

  • @priyankasetiya1358
    @priyankasetiya1358 5 หลายเดือนก่อน

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

  • @atharvsakhala9469
    @atharvsakhala9469 4 ปีที่แล้ว +2

    is their any advice you have on choosing lang for interview questions?
    is there any reason to not use python since its easiest?

    • @harshal_bh
      @harshal_bh 4 ปีที่แล้ว

      for interview you can choose any lang but you shud be well versed with it (from my interview exp)

    • @PabitraPadhy
      @PabitraPadhy 3 ปีที่แล้ว

      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.

  • @abhay6124
    @abhay6124 4 ปีที่แล้ว +1

    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

    • @shreya-rs1fr
      @shreya-rs1fr 4 ปีที่แล้ว +3

      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.

    • @mishra1576
      @mishra1576 3 ปีที่แล้ว

      @@shreya-rs1fr thnku ,the same thing I was searching for

  • @NotNotNithin
    @NotNotNithin 3 ปีที่แล้ว +5

    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);
    }
    }

    • @kushalswarup2662
      @kushalswarup2662 20 วันที่ผ่านมา

      but there is no predefined pair class in java ..?

  • @youKnowMe4real
    @youKnowMe4real ปีที่แล้ว

    in java priority queue insert in logn , as we inserting n time complexity is nlog(n)?

  • @snakifysolutions7086
    @snakifysolutions7086 2 ปีที่แล้ว +1

    What if two pairs have same absolute difference and we want to pop the pair with greater arr[i]???

    • @TanuKansal-nn4el
      @TanuKansal-nn4el 5 หลายเดือนก่อน

      I also have the same doubt

  • @nitishmishra9943
    @nitishmishra9943 4 ปีที่แล้ว +1

    Since, we are given a sorted array.....so can't we apply binary search to reduce the complexity?

  • @vikaskhangar892
    @vikaskhangar892 2 ปีที่แล้ว

    what will be the changes if i want output in order like first closest should come first ....so on

  • @tot7997
    @tot7997 ปีที่แล้ว

    can we make our comparator and sort priority_queue according to that and apply logic of k largest or smallest element

  • @kapilrules
    @kapilrules 2 หลายเดือนก่อน

    par iska complexity 0(n) ho jayega + heap ka O(n log n).

  • @mohit8299
    @mohit8299 2 ปีที่แล้ว

    Great video boss 👍 👏 👌

  • @ridimamittal4064
    @ridimamittal4064 4 ปีที่แล้ว +1

    THANK YOU !!!!!

  • @atharvsakhala9469
    @atharvsakhala9469 4 ปีที่แล้ว

    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

  • @nishantingle1438
    @nishantingle1438 2 ปีที่แล้ว +1

    Why complicate ? Why not just use something like `var maxHeap = new PriorityQueue(k, (a, b) -> Math.abs(x - b) - Math.abs(x - a))` ?

  • @sheenamunjal7821
    @sheenamunjal7821 3 ปีที่แล้ว

    your explanation is great. please solve this question in java

    • @rajitsrajan2644
      @rajitsrajan2644 3 ปีที่แล้ว

      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()

  • @raviashwin1157
    @raviashwin1157 4 ปีที่แล้ว

    Do heap of pair element take first element of q to compare ?

  • @ahipsharma
    @ahipsharma 2 ปีที่แล้ว

    Thanks a lot sir😍😍😍😍😍😍😍😍😍😍

  • @shubhamg02
    @shubhamg02 3 ปีที่แล้ว

    bhadiya question!!

  • @modiyadeepashokbhai5466
    @modiyadeepashokbhai5466 2 ปีที่แล้ว

    @Aditya verma please make video on other topics as soon as possible

  • @sejalrai30
    @sejalrai30 2 ปีที่แล้ว

    u r the best pls or videos bnaaiye

  • @vivekgopalasetty2790
    @vivekgopalasetty2790 4 ปีที่แล้ว

    what is i make size of heap before itself then what will happen if it insert element will it pop useless element by itself

  • @AkashKeserwani
    @AkashKeserwani 2 ปีที่แล้ว +4

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

  • @eshaanbhardwaj1511
    @eshaanbhardwaj1511 2 ปีที่แล้ว

    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] )_

    • @deepakkushwaha1392
      @deepakkushwaha1392 ปีที่แล้ว

      time complexity of sort in map in nlogn but in heap it's nlogk which is far far better

  • @priyanksoni1207
    @priyanksoni1207 4 ปีที่แล้ว +3

    How can I implement pairHeap in JAVA? Can anyone help me with example?

    • @sandeepm2723
      @sandeepm2723 4 ปีที่แล้ว

      you can create a class for that

    • @pavanthalla465
      @pavanthalla465 4 ปีที่แล้ว

      Can't we use tree map instead of this..

    • @devplus7131
      @devplus7131 4 ปีที่แล้ว +8

      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/

    • @sauravdas7591
      @sauravdas7591 3 ปีที่แล้ว

      @@devplus7131 just keep the link and not the solution, this will make people not work. Though I appreciate your efforts to share the link

  • @ayushthakur733
    @ayushthakur733 3 ปีที่แล้ว

    Legendary Aditya Verma

  • @IqraKhan-nk1mg
    @IqraKhan-nk1mg ปีที่แล้ว

    can u make a series on hash map

  • @parissweetheart96
    @parissweetheart96 2 ปีที่แล้ว +5

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

    • @ShubhamNigamdaadestroyer
      @ShubhamNigamdaadestroyer ปีที่แล้ว

      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

    • @abinashdash7170
      @abinashdash7170 ปีที่แล้ว

      @@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.
      */

  • @vishalt1908
    @vishalt1908 4 ปีที่แล้ว +9

    Finally channel is monetized
    2 rs ki Pepsi
    Bhai apna sexy

    • @subhamthakur565
      @subhamthakur565 4 ปีที่แล้ว

      @Zexy Turpa $ 1000 ki pepsi Bhai apna SEXY

  • @sheenamunjal7821
    @sheenamunjal7821 3 ปีที่แล้ว

    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

  • @vasudevparmar9876
    @vasudevparmar9876 3 ปีที่แล้ว

    instead of pair we can try array of size 2

  • @kishanmishra9802
    @kishanmishra9802 4 ปีที่แล้ว

    Thanks a lot sir

  • @richa6695
    @richa6695 4 ปีที่แล้ว +1

    @Aditya Can you explain the same problem with binary search?

  • @abhimanyuraizada7713
    @abhimanyuraizada7713 ปีที่แล้ว

    What is the TC?

  • @RajveerSingh-yf1os
    @RajveerSingh-yf1os 9 หลายเดือนก่อน

    it will work only for O(nlogk) so dont worry

  • @tejasharishborkar3754
    @tejasharishborkar3754 4 ปีที่แล้ว +2

    OP bro👏👏

  • @rishabhsingh5821
    @rishabhsingh5821 3 ปีที่แล้ว +1

    Ek value hi rakho ...7 add karke output dikha do ...ye bhi to possible h

  • @nityanandbhaskar2155
    @nityanandbhaskar2155 4 ปีที่แล้ว

    thanks a lot

  • @ajwaddddd
    @ajwaddddd ปีที่แล้ว

    what is time complexity?

  • @devendrasingh4776
    @devendrasingh4776 4 ปีที่แล้ว +2

    If we have to do in logn and 0(1) space then

    • @ojasvichaudhary8724
      @ojasvichaudhary8724 3 ปีที่แล้ว

      binary search
      find the position of x then ( position-k )and (position+k ) contains our answer

  • @editorera239
    @editorera239 3 ปีที่แล้ว +1

    Is this a binary search problem

  • @pranaydwivedi4002
    @pranaydwivedi4002 4 ปีที่แล้ว +1

    Can we insert a pair of values inside heap in java ? If any one know please reply.

    • @ankurgupta4696
      @ankurgupta4696 4 ปีที่แล้ว

      i also have same question

    • @ankurgupta4696
      @ankurgupta4696 4 ปีที่แล้ว +1

      well using treemap we can implement it in java

    • @subhamthakur565
      @subhamthakur565 4 ปีที่แล้ว +1

      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

    • @AmitKumar-hq4wb
      @AmitKumar-hq4wb 4 ปีที่แล้ว

      @@subhamthakur565 bro can u help me with python code for this problem...I m stuck

    • @dysonfilmstw4764
      @dysonfilmstw4764 3 ปีที่แล้ว

      @@AmitKumar-hq4wb Did u get the python code ? or you still need it

  • @atharvsakhala9469
    @atharvsakhala9469 4 ปีที่แล้ว

    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.

    • @shuvamchaturvedi4443
      @shuvamchaturvedi4443 4 ปีที่แล้ว +1

      NO we can push a tuple I python heapq library.. for e.g "heapq.heappush(li,(4,100))"

    • @prateekgoel5344
      @prateekgoel5344 2 ปีที่แล้ว

      Why You Need to push a tuple you can push a list also.

  • @ankurgupta4696
    @ankurgupta4696 4 ปีที่แล้ว +2

    java mai pair kaise banate hai??

    • @subhamthakur565
      @subhamthakur565 4 ปีที่แล้ว +2

      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());
      }



      }
      }

    • @youryuvv
      @youryuvv 4 ปีที่แล้ว

      @@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 .

  • @shellachaurasia5289
    @shellachaurasia5289 3 ปีที่แล้ว

    Gajab bhai

  • @palakdavda2628
    @palakdavda2628 4 ปีที่แล้ว +2

    Please provide a solution in java aswell

    • @rajitsrajan2644
      @rajitsrajan2644 3 ปีที่แล้ว

      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()

  • @louerleseigneur4532
    @louerleseigneur4532 4 ปีที่แล้ว +2

    merci

  • @Shourya_performs
    @Shourya_performs 2 ปีที่แล้ว

    can someone give the ques link?

  • @ramanprasad5857
    @ramanprasad5857 3 ปีที่แล้ว

    how we can solve this particular problem using python

  • @luvgupta8495
    @luvgupta8495 2 ปีที่แล้ว +4

    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() + " ");
    }
    }

    • @developer-cminiclip8745
      @developer-cminiclip8745 2 ปีที่แล้ว

      Bro yeh max heap kaise bnai apne ...plz btana....maths.abs sai confusion ho rha hai...plz reply

    • @luvgupta8495
      @luvgupta8495 2 ปีที่แล้ว

      @@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

    • @ShubhamNigamdaadestroyer
      @ShubhamNigamdaadestroyer ปีที่แล้ว

      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

    • @chitranshsrivastava5880
      @chitranshsrivastava5880 ปีที่แล้ว

      @@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

  • @himu1901
    @himu1901 2 ปีที่แล้ว

    first pair will be sorted automatically

  • @bishalsingh4147
    @bishalsingh4147 3 ปีที่แล้ว

    how to create a pairing heap in python plz help

    • @derilraju2106
      @derilraju2106 ปีที่แล้ว

      push as a tuple, it will build the heap based on the first element

  • @rudrakhare1158
    @rudrakhare1158 6 หลายเดือนก่อน

    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

  • @ayush7518
    @ayush7518 2 ปีที่แล้ว

    can someone plaese tell me how to use pair in java.
    or provide the complete code in java.

    • @chitranshsrivastava5880
      @chitranshsrivastava5880 ปีที่แล้ว

      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

  • @shuvamchaturvedi4443
    @shuvamchaturvedi4443 4 ปีที่แล้ว

    how to do this pair thing in heap in python..pls help anyone!!

  • @yatin3699
    @yatin3699 2 ปีที่แล้ว +1

    can anyone give me the c++ code

  • @sarthakbharadwaj-pq4hl
    @sarthakbharadwaj-pq4hl 4 หลายเดือนก่อน

    graphhhhhh

  • @Saurabh-fe2bg
    @Saurabh-fe2bg 2 ปีที่แล้ว

    someone please paste java code wasted an hour still cant figure out

  • @DSA_Coding
    @DSA_Coding 3 ปีที่แล้ว

    hats down

  • @vanditkhuranapvt
    @vanditkhuranapvt 4 ปีที่แล้ว +2

    Please tell the syntax of Paired PriorityQueue in Java

    • @rajitsrajan2644
      @rajitsrajan2644 3 ปีที่แล้ว +2

      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()

    • @vanditkhuranapvt
      @vanditkhuranapvt 3 ปีที่แล้ว +1

      @@rajitsrajan2644 Bro abb toh placement bhi ho gyi... thanks btw 😀

    • @rajitsrajan2644
      @rajitsrajan2644 3 ปีที่แล้ว +1

      Maybe it will come handy in next interview😅😝

  • @namashsharma7550
    @namashsharma7550 ปีที่แล้ว

    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
      @siddwivedi9643 ปีที่แล้ว

      bhaii java me pair ki class banani pdegi , aur class banana java me basic cheez hai ...Phle basics clear kro !!

    • @namashsharma7550
      @namashsharma7550 ปีที่แล้ว +1

      @@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.

  • @kishorjha5028
    @kishorjha5028 3 ปีที่แล้ว

    op exlanation

  • @sarveshkumar-fu3ub
    @sarveshkumar-fu3ub 3 ปีที่แล้ว

    first like then i watch the video..

  • @sindhukambam
    @sindhukambam 2 ปีที่แล้ว

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

  • @ishansingh7267
    @ishansingh7267 3 ปีที่แล้ว

    bhai isi ke company mein aane ke liye!!

  • @onehp9759
    @onehp9759 3 ปีที่แล้ว

    guru ji bit pe videos bana do

  • @rijuljethani6218
    @rijuljethani6218 2 ปีที่แล้ว +3

    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)

    • @Manoj2382
      @Manoj2382 ปีที่แล้ว +1

      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.