New update is available. Click here to update.

Running Median

PROBLEM STATEMENT

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

Approach 2

According to the previously discussed approach, every time there is a new addition, we have a sorted array right before the addition. Instead of sorting it again, we can simply insert this new element in the right position. The new array thus formed will still be sorted.

Now we can find median through the middle positions of sorted array.

Try Problem

Approach 3

The idea is to maintain two equal halves of the current stream: the higher half containing greater valued elements, and the lower half containing lower valued element. For each new addition, the transition between elements in the two halves goes this way:

If the new element is less than the maximum element of the lower half, then this element gets added to the lower half.

After the addition, if the difference between the sizes of the two halves becomes greater than 1, then to maintain the balance, the maximum element is removed from the lower half and added to the higher half.

2. If the new element is greater than the maximum element of the lower half, then this element gets added to the higher half.

Now, if the difference between the sizes of the two halves becomes greater than 1, to maintain balance, the minimum element of the higher half is removed and added to the lower half.

By maintaining the halves in this way, we assure that the elements of the stream are equally distributed between the two halves.

Hence, after each addition the maximum element of the lower half and the minimum element of the higher half become the middle-most elements, which we can use to compute the median.
Considering the odd elements case, whichever half has more elements, the maximum of lower half or minimum of higher half will be the median.
Considering the even elements case, average of maximum of lower half and minimum of higher half will be the median.
How can we store these elements in a way that supports this functionality? We can create a max heap for the lower half, and a min heap for the upper half.

Try Problem