Can you please tell where i m going wrong
Hey @haseebshaik00
You have to solve it using max_heap such that both pop and push becomes direct operation
Refer to this if required 
For every query of type 1, insert elements until the size of the heap becomes ‘k’.
Then for every query of type 1 after reaching the size k for heap(max-heap) we will check if the current element is smaller than the root of the heap or not. If it is not smaller then we ignore it else we remove the root of the heap and push the new element in the heap. (What this will do is maintain a heap of size k which will contain k nearest coordinates for the dean) .
For every query of type 2 just print the root of the heap.
Cant understand !!!
Hey @haseebshaik00
Let us try to dry run the sample testcase for a better understanding
Sample Input:
9 3
1 10 10
1 9 9
1 -8 -8
2
1 7 7
2
1 6 6
1 5 5
2
Sample Output:
200
162
98
Here ,
No of queries = n = 9
k = 3
We have to print the kth distance from the hotel.
We are calculating and storing the rocket distance here i.e. (x2-x1)^2 + (y2-y1)^2 … basically the cartesian distance but without the squareroot.
First integer of each input defines the query type. 1 means take the coordinates input and 2 means display the kth distance so far.
Iteration 1 :
First we get 1 10 10
Distance = 10^2 + 10^2 = 200
We store it in our array or heap or whatever data structure we are using . Lets call it A.
A = { 200 }
Iteration 2 :
1 9 9
Distance = 9^2 + 9^2 = 162
A = { 200,162 }since max heap
Iteration 3 :
1 -8 -8
Distance = (-8)^2 + (-8)^2 = 168
A = { 200 ,162,128}
Iteration 4 :
2
A = { 200 ,162,128}
Time to print the 3rd nearest distance which is at root
Output : 200
Iteration 5 :
1 7 7
Distance = 7^2 + 7^2 = 98
since smaller than root , remove root and push it because we will always mantain k elements
A = { 162,128,98}
Iteration 6 :
2
A = { 162,128,98}
Time to print the 3rd nearest distance ( k=3) which is at root
Output : 162
Iteration 7 :
1 6 6
Distance = 6^2 + 6^2 = 72
since smaller than root , remove root and push it because we will always mantain k elements
A = { 128,98,72}
Iteration 8 :
1 5 5
Distance = 5^2 + 5^2 = 50
since smaller than root , remove root and push it because we will always mantain k elements
A = { 98,72,50}
Iteration 9 :
2
A = { 98,72,50}
Time to print the 3rd nearest distance ( k=3 )
Output : 98
Final Output :
200
162
98
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.