TLE and 3 Test Case Not Passing

#1

problem: hostel visits
https://online.codingblocks.com/app/player/69347/content/128048/5368/code-challenge

sol:

#2

hello @Shrey0709
use long long for i and j.

#3

@aman212yadav i converted the vector and i,j into ll int , it’s working fine but last case is giving TLE. updated code:

#4

try to optimise ur approach
hint -> max heap

#5

I tried thinking of that but won’t popping of more elements let’s say 100 from max heap to reach the 3rd lowest value will take O(log n) time and then storing will take 0(1) for N elements pushing them again in max heap will take O(log n) for inserting 100 elements again , and in case of min heap we just need to pop first 3 elements and add again which will take same log n + log n time , but since elemnets to pop and push are much smaller in number , so won’t min heap be effective ?

I am not able to approch this issue using max heaps

#6

@Shrey0709

approach ->
image

code->

image
image433×540 8.9 KB

we are always maintaining our heap size equal to k.
if we are finding any hostel whose distance is smaller than current kth smallest(i.e pq.top())
then we are popping current kth smallest from the heap and pushing the new hostel in place of that.

do a dry on pen and paper u will get the idea

#7

Thanks a lot !
Got it .

#8

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.