 New update is available. Click here to update.

# Running Median

Last Updated: 18 Aug, 2017
Difficulty: Hard

## PROBLEM STATEMENT

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