Hostel visit problem

#1

Im getting a tle for second case

#2

@sounakume because in second case your algo is going to take O(k) time for finding the answer and overall time complex. will be O(q*k).

So you have to optimize your solution.
Take a max queue of size k, where the top element will be the kth largest distance which will give the answer for second case in O(1).
So for maintaining the queue in case 1, check 2 conditions:-

  1. if the number of elements in queue is less than k, then insert that point.
  2. If size of queue is k, then compare it with top and if the current point is at less distance than pop the top and insert the current dist.
1 Like