Median in a stream

Hard
0/120
Average time to solve is 50m
profile
Contributed by
154 upvotes
Asked in companies
Disney + HotstarAmazonMakeMyTrip

Problem statement

Given that integers are read from a data stream. Your task is to find the median of the elements read so far.

Median is the middle value in an ordered integer list. If the size of the list is even there is no middle value. So the median is the floor of the average of the two middle values.

For example :
[2,3,4] - median is 3.
[2,3] - median is floor((2+3)/2) = 2.


Detailed explanation ( Input/output format, Notes, Images )
Input Format:
The first line of input contains a single integer T, representing the number of test cases or queries to be run. 

Then the T test cases follow.
The first line of each test case contains the number of elements, N, in the input data stream.

The second line of each test case contains N space separated elements of the input data stream.
Output Format:
For each test case, print the median of the elements after each incoming element. Each median value is separated by a single space.

The output of each test case is printed in a separate line.
Note :
You do not need to print anything, just return the vector of medians after each element is read from the stream. 
Constraints :
1 <= T <= 10
1 <= N <= 10^4
0 <= data <= 10^8
Where T is the number of test cases, N is the number of elements in the data stream.

Time Limit : 1 sec
Sample Input 1:
3
3
1 2 3 
2
9 9 
1
4 
Sample Output 1:
1 1 2
9 9 
4 
Explanation for Sample Input 1:
For test case 1 
After reading first element of stream , Median of [1] is 1 
After reading second element of stream, Median of [1, 2]  = floor((1+2)/2)  = 1
After reading third element of stream, Median of [1,2,3] = 2
So the output will be 1 1 2.
Sample Input 2:
2
3
5 3 8
2
3 8
Sample Output 2:
5 4 5
3 5
Explanation for Sample Input 2:
For test case 1 
After reading first element of stream, Median of [5] is 5
After reading second element of stream, Median of [5, 3]  = floor((5+3)/2)  = 4
After reading third element of stream, Median of [5,3,8] = 5 , it is the middle value of the sorted array
So the output will be 5 4 5.
Hint

Do what the question says.

Approaches (3)
Brute force approach

Store the incoming data elements in a vector. Sort the vector everytime you need to output the median.

Algorithm:

  1. Store the incoming elements of the data stream in a vector.
  2. Step by step insert one element and sort the vector as soon as any element is added in the vector.
  3. If the size of the vector is odd, print the middle element of the sorted vector.
    If the size of the vector is even, return the mean of the middle two elements of the sorted vector.
Time Complexity

O(N*(N*log(N))), Where N is the number of elements in the data stream.

 

The algorithm uses inbuilt sorting algorithm to sort the vector. So, for sorting time complexity will be N*log(N). The vector is sorted for every element of the data stream. So, the final time complexity of the algorithm is O(N*(N*(log(N))).

Space Complexity

O(N), where N is the number of elements in the data stream.

 

Since the algorithm stores every element of the data stream in a vector, which requires O(N) space.

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Median in a stream
Full screen
Console