The brute force approach would be to first sort the list and then for each query return the element in the center. For each insertion in the list find its proper place and shift all the elements to its right by one. But this solution is not optimal and will give TLE. Can you think of a better approach ?
Median is defined as the element in the center of a sorted list. So we can say that half of the numbers in the list are less than the median whereas the other half is greater than the median. Hence we will maintain two separate lists of numbers : the upper half and the lower half. Whenever a new number comes up we will determine in which half it belongs. Also another thing to take care of is that the difference in the size of the lists should never be greater then 1 since they are a representation of two halves of the list(and hence should be equal in size).
The lower half of numbers can be implemented using a max heap and the upper half using min heap. Insertion will take log n time and the median query will also take log n time. Thus the complexity of this solution will be O(n log n). Since the time limit of the problem is very strict it is better to use printf/scanf instead of cin/cout for faster I/O.
Solution: Online C++ Compiler & Debugging Tool
Read more… (245 words)
