New update is available. Click here to update.

Last Updated: 18 Aug, 2017

Difficulty: Hard

```
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.
```

```
Print the running median for every integer added to the running list in one line (space-separated).
```

```
0 <= N <= 10 ^ 5
1 <= ARR[i] <= 10 ^ 5
Time Limit: 1 sec
```

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.

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.

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.

SIMILAR PROBLEMS

Min Heap

Posted: 5 May, 2022

Difficulty: Moderate

Max tasks in the given Budget

Posted: 10 Jun, 2022

Difficulty: Moderate

Time to publish comic books

Posted: 10 Jun, 2022

Difficulty: Moderate

Min Heap Implementation

Posted: 22 Jun, 2022

Difficulty: Moderate

Find Median from Data Stream

Posted: 9 Sep, 2022

Difficulty: Moderate

Popular Interview Problems: