Please help to solve this…
How to solve spoj Running Median(RMID) problem using two heaps
Hint 1: Use 1 max and 1 min heap.
(Think hard before proceeding to next hint)
Hint 2: Where does the median lies in the sorted set of integer(in the middle duh…
). What if you can divide the unsorted set of integers in 2 halves, one which lies on the left of median(i.e having numbers smaller than median) and one which lies on the right of median in the final sorted set without sorting all the numbers together ? Then you can say the number which lies in midway, and is greater than all the numbers in first half and smaller than all the numbers in second half is the required median itself, isn’t it?
Try to think harder, ask me again if you get stuck, I have deliberately not shared the exact solution now, it would be better if you come up with it yourself, and if you need more hints, ask me again…
1 Like