Running Median

Hard
0/120
Average time to solve is 46m
profile
Contributed by
55 upvotes
Asked in companies
AmazonOYOHike

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
6
6 2 1 3 7 5
Sample Output 1 :
6 4 2 2 3 4
Explanation of Sample Output 1 :
S = {6}, median = 6
S = {6, 2} -> {2, 6}, median = 4
S = {6, 2, 1} -> {1, 2, 6}, median = 2
S = {6, 2, 1, 3} -> {1, 2, 3, 6}, median = 2
S = {6, 2, 1, 3, 7} -> {1, 2, 3, 6, 7}, median = 3
S = {6, 2, 1, 3, 7, 5} -> {1, 2, 3, 5, 6, 7}, median = 4
Sample Input 2 :
5
5 4 3 2 1
Sample Output 2 :
5 4 4 3 3
Hint

After every new addition to the stream, how do we find the middle-most elements?

Approaches (3)
Sorting Approach

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.

Time Complexity

O(N * N * log(N)), where N is the number of elements in the array.

 

There are N additions, and after each addition, we sort the numbers, which takes O(N * log(N)) time. Hence, the overall Time Complexity is O(N * N * log(N)).

Space Complexity

O(1).

 

Constant space is being used. Hence, the overall Space Complexity is O(1).

Code Solution
(100% EXP penalty)
Running Median
Full screen
Console