Running Median

Posted: 18 Aug, 2017
Difficulty: Hard


Try Problem

You are given a stream of 'N' integers. For every 'i-th' integer added to the running list of integers, print the resulting median.

Print only the integer part of the median.

Input Format :
The first line of input contains an integer 'N', denoting the number of integers in the stream.

The second line of input contains 'N' integers separated by a single space.
Output Format :
Print the running median for every integer added to the running list in one line (space-separated).
Input Constraints
0 <= N <= 10 ^ 5
1 <= ARR[i] <= 10 ^ 5

Time Limit: 1 sec
Approach 1

The median of n numbers is the middle-most element among the numbers when sorted in ascending order, when n is odd, and is the average of the two middle-most elements, when n is even. To find the middle-most elements, we do this: For every new addition to the stream, we sort all the numbers that are currently present. This makes it easy for us to obtain the middle-most elements.

Try Problem