Hostel Visit doubt

#1

Can I solve it by Heap DS?

#2

hi @Kinjal you can do this question with the help of a max heap

#3

Hi @Ishitagambhir
Yes. You’re right.

#4

@Kinjal the above code is absolutely correct! Is there anything else I can help you with?

#5

My concern is the way “Hostel Visit” question asks.
It says,

second type : 2 For query of 2nd type, you have to output the Rocket distance of Kth nearest hostel till now.

So if I use max heap and if my input is like:
4 3
1 -8 -8
1 9 9
1 10 10
2
Then according to question, Kth nearest hostel will be 128.
But if I use max Heap then it will be 200.
Right!!!

#6

@Kinjal in the max heap you have to store the k nearest hostels only, so that heap.top() will give you the farthest (ie the kth distance) hostel

Also for the input you’ve provided, rocket distances are
128, 162, 200 (in inc order)
and k = 3
so 3rd nearest hostel is 200
128 is the 1st nearest hostel

#7

what if, my input is like:
4 3
1 10 10
1 9 9
1 -8 -8
2
Then, my 3rd nearest hostel will be 128, right!

#8

@Kinjal how will the 3rd nearest hostel be 128? Order of the input doesn’t matter you have to sort the distances anyway, you cant say any random distance is at kth number, you have to sort all the distances and then see which one is at the kth number

1 Like
#9

Why I have to sort all the distances?

#10

Got it!!! I have to sort all the distances because Dean wants to go K nearest hostels from where he lives.

#11

@Kinjal yes that’s right

#12

Thanks @Ishitagambhir

#13

@Kinjal please mark your doubt as resolved!