1 test case is passed but giving TLE for 2nd test case

#1
#2

hi @dishant_rahangdale you have to use a max-heap in this question.
Keep only k elements in the queue, so that pq.top() will give you the kth farthest hostel for each query. Let me know if you need any help with the logic

#3

in question, we have to print kth hotel not farthest and also in explanation section they keeps all hotel distance in queue not only 3 element

#4

@dishant_rahangdale if you use a max heap, and keep only the k minimum elements in it, pq.top() will automatically give you the kth hotel. Just try to dry run with this logic once you will get the intuition.

For query of type 1, if size of heap is less than k, insert distance. If size of heap is more than or equal to k, in this case, if the top element is larger than the current distance, pop that distance from the queue and push the current distance, else do nothing. This will ensure that k nearest distances remain in the heap and because the heap is max heap, kth largest distance will be given by pq.top()
Therefore, for queries of type 2, print the top element of the queue.

for the example

4 3
1 2 2
1 9 9
1 -8 -8
2

q = 4, k = 3
so the max size of the heap can be 3
1 2 2 -> insert 8 in the heap
1 9 9 -> insert 162 in the heap
1 -8 -8 -> insert 128 in the heap

Now, if you look at all the distances from origin, they are {8, 128, 162}
Third nearest hostel is 162

#5

( https://ide.codingblocks.com/s/295830 ) i edited the code getting correct output but test cases getting failed

#6

@dishant_rahangdale the distance x*x+y*y can be very large so use long long datatype

#7

still getting failed test cases with long long distance

#8

@dishant_rahangdale you didnt change the datatype of priority queue, or x and y.

#9
#10

@dishant_rahangdale this part is conditional
image

see this

#11

https://ide.codingblocks.com/s/295845 ma’am i am still getting test case failed. please edit code

#12

@dishant_rahangdale try now https://ide.codingblocks.com/s/295868

#13

again, only 1st test case is getting passed with the code that you provided. 2nd test case is still getting failed

#14

@dishant_rahangdale you shared the int code again and I made changes in that only, take the code I sent and use long long datatype in it, it should work

#15
#16

@dishant_rahangdale https://ide.codingblocks.com/s/295903

#17

now they are correct thank you Ma’am

1 Like