5 K Closest Numbers

Given an unsorted array and two numbers x and k, find k closest values to x.
Input : arr[] = {10, 2, 14, 4, 7, 6}, x = 5, k = 3 .
------------------------------------------------------------------------------------------
Here are some of the gears that I use almost everyday:

PS: While having good gears help you perform efficiently, don’t get under the impression that they will make you successful without any hard work.

[tanboyy]

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

[mohitzen]

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.

[manishakhanchandani]

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

[Pratik-Kedar]

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<int, bool> and set the bool is equal to true when difference is negative.
Ans while returning add that value to X if bool is set.

[vikashkumarchaurasia]

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

[AlbertoRodriguez-oejo]

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.

[shashwatmishra]

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.

[manjushajagtap]

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

[BikkiMahato]

// K Closest Numbers

import java.util.Collections;
import java.util.PriorityQueue;

class Pair implements Comparable<Pair> {
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<Pair> maxHeap = new
for (int i : arr) {
maxHeap.add(new Pair(Math.abs(i - x), i));
if (maxHeap.size() > k) {
maxHeap.poll();
}
}
while (maxHeap.size() > 0) {
+ " ");
}
}
}

[vikashkumarchaurasia]

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

[priyankasetiya]

class Pair{
Integer first;
Integer second;
Pair(Integer first, Integer second){
this.first = first;
this.second = second;
}
}
class Solution {
public List<Integer> findClosestElements(int[] arr, int k, int x) {
List<Integer> list = new ArrayList<>();
PriorityQueue<Pair> 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;i<arr.length;i++){
Integer first= Math.abs(arr[i]-x);
Integer second=arr[i];
pq.add(new Pair(first, second));
if(pq.size()>k){
pq.poll();
}
}

while(!pq.isEmpty()){
list.add(pq.peek().second);
pq.poll();
}
Collections.sort(list);
return list;

}
}

[shiwangisharma]

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?

[AnkushKumar-mkns]

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

[ytsh]

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

[imPriyansh]

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

[heenaagarwal]

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?

[JigsawXop]

class Solution {
public:
vector<int> printKClosest(vector<int> arr, int n, int k, int x) {
priority_queue<pair<int, int>> maxH; // Max-heap stores (difference, element)

// Push elements into the heap
for (int i = 0; i <n; i++) {
if (arr[i] == x)
continue;
maxH.push({abs(arr[i] - x), arr[i]}); // Push (absolute difference, element)
if (maxH.size() > k) {
maxH.pop(); // Remove the farthest element if size exceeds k
}
}

// Extract elements from the heap
vector<int> ans;
while (!maxH.empty()) {
// Collect the elements
maxH.pop();
}

// Sort the result
// Sort in ascending order
reverse(ans.begin(), ans.end());
return ans;
}
};

[dikshabharti]

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

[remedyiq]

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

[AkhilNairjedi]

Instead of using pair<int, int> we could use our own compare function instead.


template<int k>
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<int, vector<int>, Compare<5> > pq;