the key idea is to use the quicksort partitioning scheme in which we reduce our selection problem size into half(just the expectation).
T(n) = O(n) + T(n // 2)
the resulting algrithm is a O(n) algo…
if anyone faced a problem similar to RMID2 but having very less queries but large data stream then it is better to use the randomized selection’s
O(1) insertion and
O(n) query rather than two priority queue method’s
O(log(n)) insertion and
here’s my implementation..