Median in a stream
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.

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

Question

Median in a stream

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.

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

Accepted Answer

Brute force approach

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

Algorithm:

Store the incoming elements of the data stream in a vector.
Step by step insert one element and sort the vector as soon as any element is added in the vector.
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.

Space Complexity: O(n)Explanation:

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.

Time Complexity: O(n^2logn)Explanation:

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

C++ (g++ 5.4)

/*



	Time complexity: O(N*(N*log(N))) 

	Space complexity: O(N)

	

	where N is the total number of elements in the array.



*/



#include 



vector findMedian(vector &arr, int n){

	

	// To store the incoming stream elements

	vectorstore;

	

	// To store the medians

	vector medians;

	

	for(int i = 0; i < n; i++){

		

		// Storing the incoming data from stream in a vector 'store'

		store.push_back(arr[i]);

		

		// Sorting the vector to arrange all the elements in sorted order

		sort(store.begin(),store.end());

		

		int median;

		// Even number of elements are read, (Note - 0 based indexing is used)

		if((i+1)%2==0){

			

			// Average of middle two values

			median = (store[i/2] + store[(i+1)/2])/2;

				

		}

		// odd number of elements are read

		else{

			

			// The middle value of the sorted arrangement of the elements read so far

			median = store[i/2];

			

		}

		

		medians.push_back(median);

		

	}

	

	return medians;

}

Java (SE 1.8)

/*



	Time complexity: O(N*(N*log(N))) 

	Space complexity: O(N)

	

	where N is the total number of elements in the array.



*/



import java.util.ArrayList;

import java.util.Collections;



public class Solution {

    public static int[] findMedian(int[] arr, int n) {



        // To store the incoming stream elements

        ArrayList store = new ArrayList();



        // To store the medians

        int[] medians = new int[n];



        for (int i = 0; i < n; i++) {



            // Storing the incoming data from stream in a vector 'store'

            store.add(arr[i]);



            // Sorting the vector to arrange all the elements in sorted order

            Collections.sort(store);



            int median;

            // Even number of elements are read, (Note - 0 based indexing is used)

            if ((i + 1) % 2 == 0) {



                // Average of middle two values

                median = (store.get(i / 2) + store.get((i + 1) / 2)) / 2;



            }

            // odd number of elements are read

            else {



                // The middle value of the sorted arrangement of the elements read so far

                median = store.get(i / 2);



            }



            medians[i] = (median);



        }



        return medians;

    }

}

Python (3.5)

'''

	Time complexity: O(N*(N*log(N)))

	Space complexity: O(N)



	where N is the total number of elements in the array.



'''





def findMedian(arr, n):



    # To store the incoming stream elements

    store = []



    # To store the medians

    medians = []



    for i in range(n):

        # Storing the incoming data from stream in a vector 'store'

        store.append(arr[i])



        # Sorting the vector to arrange all the elements in sorted order

        store.sort()



        median = 0

        # Even number of elements are read, (Note - 0 based indexing is used)

        if((i+1) % 2 == 0):



            # Average of middle two values

            median = (store[i//2] + store[(i+1)//2]) // 2



        # odd number of elements are read

        else:



            # The middle value of the sorted arrangement of the elements read so far

            median = store[i//2]



        medians.append(median)



    return medians

Accepted Answer

Insertion sort approach

If we sort the data as it appears, the median can be located easily. Insertion Sort is one such algorithm that sorts the data appeared so far. At any instance of sorting, say after sorting i-th element, the first ‘i’ elements of the array are sorted. Insertion sort considers data sorted so far while inserting the next element.

Algorithm:

Store the incoming elements in a vector.
Use insert operation of insertion sort to sort the elements step by step calculating medians.
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.

Space Complexity: O(n)Explanation:

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.

Time Complexity: O(n^2)Explanation:

O(N^2), Where N is the number of elements in the data stream.

The algorithm uses insertion sort algorithm to sort the vector. So, for sorting time complexity will be N^2. So, the final time complexity of the algorithm is O(N^2).

Python (3.5)

'''



	Time complexity: O(N*N)

	Space complexity: O(N)



	where N is the total number of elements in the array.



'''





def findMedian(arr, n):



    # To store the incoming elements

    store = []



    # To store the medians

    medians = []



    for i in range(n):



        # Insert the new element in the store vector

        store.append(arr[i])



        # shift it at its sorted position in store

        j = 0



        while(j < i):



            if(store[j] <= arr[i]):

                j += 1



            else:

                break



        # Shifting all the elements greater than the current element to the right



        k = i-1



        while(k >= j):



            store[k+1] = store[k]

            k -= 1



        # Inserting the current element at its sorted position

        store[j] = arr[i]



        median = 0

        # Even number of elements are read, (Note - 0 based indexing is used)

        if((i+1) % 2 == 0):



            # Average of middle two values

            median = (store[i//2] + store[(i+1)//2]) // 2



        # odd number of elements are read

        else:



            # The middle value of the sorted arrangement of the elements read so far

            median = store[i//2]



        medians.append(median)



    return medians

Java (SE 1.8)

/*



   Time complexity: O(N*N) 

   Space complexity: O(N)



   where N is the total number of elements in the array.



*/



import java.util.ArrayList;



public class Solution {

    public static int[] findMedian(int[] arr, int n) {



        // To store the incoming stream elements

        ArrayList store = new ArrayList();



        // To store the medians

        int[] medians = new int[n];



        for (int i = 0; i < n; i++) {



            // Insert the new element in the store vector

            store.add(arr[i]);



            // shift it at its sorted position in store

            int j = 0;



            while (j < i) {



                if (store.get(j) <= arr[i]) {

                    j++;

                } else {

                    break;

                }



            }



            // Shifting all the elements greater than the current element to the right



            int k = i - 1;



            while (k >= j) {



                store.set(k + 1, store.get(k));

                k--;



            }



            // Inserting the current element at its sorted position

            store.set(j, arr[i]);



            int median;

            // Even number of elements are read, (Note - 0 based indexing is used)

            if ((i + 1) % 2 == 0) {



                // Average of middle two values

                median = (store.get(i / 2) + store.get((i + 1) / 2)) / 2;



            }

            // odd number of elements are read

            else {



                // The middle value of the sorted arrangement of the elements read so far

                median = store.get(i / 2);



            }



            medians[i] = (median);



        }



        return medians;



    }



}

C++ (g++ 5.4)

/*



	Time complexity: O(N*N) 

	Space complexity: O(N)

	

	where N is the total number of elements in the array.



*/



vector findMedian(vector &arr, int n){

	

	//To store the incoming elements

	vector store;

	

	// To store the medians

	vector medians;

	

	for(int i = 0; i < n; i++){

		

		// Insert the new element in the store vector 

		store.push_back(arr[i]);

		

		// shift it at its sorted position in store

		int j = 0;

		

		while(j < i){

			

			if(store[j] <= arr[i]){

				j++;	

			}

			else{

				break;

			}

			

		}

		

		// Shifting all the elements greater than the current element to the right 

		

		int k = i-1;

		

		while(k >= j){

			

			store[k+1] = store[k];

			k--;

			

		}

		

		// Inserting the current element at its sorted position

		store[j] = arr[i];

			

		int median;

		// Even number of elements are read, (Note - 0 based indexing is used)

		if((i+1)%2==0){

			

			// Average of middle two values

			median = (store[i/2] + store[(i+1)/2])/2;

				

		}

		// odd number of elements are read

		else{

			

			// The middle value of the sorted arrangement of the elements read so far

			median = store[i/2];

			

		}

		

		medians.push_back(median);

				

	}

	

	return medians;

}

Accepted Answer

Heap based approach

The idea is to use two heaps, one max - heap and one min - heap. The max-heap will be used to represent elements that are less than the effective median, and min-heap will be used to represent the elements that are greater than the effective median.
After processing the incoming element, the number of elements in heaps differ utmost by 1 element and this will be the case when there are odd number of elements. Thus the heap having more number of elements will give its root value as median. When both the heaps contains same number of elements, average of heaps root data is the effective median.

Algorithm:

Two heaps :
a. Max-heap ‘lo’ for storing the smaller half of numbers.
b. Min-heap ‘hi’ for storing the larger half of numbers.
The max-heap ‘lo’ is allowed to store, at worst, one element more than the min-heap ‘hi’.
If ‘K’ elements have been processed:
a. If ‘K’ is odd then ‘lo’ will have one more element than ‘hi’.
b. If ‘K’ is even then both the heaps will have an equal number of elements.
Thus in case a) root of ‘lo’ will give us the median and in case b) the average of the roots of both the heaps will be the median.
Adding a number num :

a. Add num to max-heap ‘lo’. Since ‘lo’ received a new element, we must do a balancing step for ‘lo’ and offer its largest element to ‘hi’.

b. The min-heap ‘hi’ might end up holding more elements than max-heap ‘lo’, after previous operation. We fix that by removing the smallest element from ‘hi’ and offering it to ‘lo’.

Space Complexity: O(n)Explanation:

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 heap, which requires O(N) space.

Time Complexity: O(nlogn)Explanation:

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

At worst there are 3 heap insertions and 2 heap deletions from top. Each of these operations take log(N) time. Thus for N elements time complexity will be O(N*(5*(log(N))) = O(N*log(N)).

C++ (g++ 5.4)

/*



	Time complexity: O(N*(log(N))) 

	Space complexity: O(N)

	

	where N is the total number of elements in the array.



*/



#include 



vector findMedian(vector &arr, int n){

	

	// To store the medians

	vector medians;

	

	// max heap

	priority_queue lo;  

	

	//min heap                            

    priority_queue, greater> hi;   

    

    for(int i = 0; i < n; i++){

    	

    	int num = arr[i];

    	

    	// Add to max heap

    	lo.push(num);                                

		

		// Balancing step, that is inserting the current element at its position that is either less than median or more than median value

        hi.push(lo.top());                        

        lo.pop();



		// Maintain size property, as 'lo' can have utmost one more element than 'hi' or both have equal number of elements

        if (lo.size() < hi.size()) {                    

            lo.push(hi.top());

            hi.pop();

        }

        

        int median;

        

        // For odd number of elements

        if(lo.size() > hi.size()){

        	

        	median = lo.top();

        	

		}

		// For even number of elements

		else{

			

			median = (lo.top() + hi.top())/2;  

			

		}

        

    	medians.push_back(median);

	}

	

	return medians;



	

}

Java (SE 1.8)

/*



	Time complexity: O(N*(log(N))) 

	Space complexity: O(N)

	

	where N is the total number of elements in the array.



*/



import java.util.PriorityQueue;

import java.util.Collections;



public class Solution {



    public static int[] findMedian(int[] arr, int n) {



        // To store the medians

        int[] medians = new int[n];



        // min heap

        PriorityQueue lo = new PriorityQueue<>();



        // max heap

        PriorityQueue hi = new PriorityQueue<>(Collections.reverseOrder());



        for (int i = 0; i < n; i++) {



            int num = arr[i];



            // Add to max heap

            lo.add(num);



            // Balancing step, that is inserting the current element at its position that is

            // either less than median or more than median value

            hi.add(lo.poll());



            // Maintain size property, as 'lo' can have utmost one more element than 'hi' or

            // both have equal number of elements

            if (lo.size() < hi.size()) {

                lo.add(hi.poll());



            }



            int median;



            // For odd number of elements

            if (lo.size() > hi.size()) {



                median = lo.peek();



            }

            // For even number of elements

            else {



                median = (lo.peek() + hi.peek()) / 2;



            }



            medians[i] = median;

        }



        return medians;



    }



}

Python (3.5)

'''



	Time complexity: O(N*(log(N)))

	Space complexity: O(N)



	where N is the total number of elements in the array.



'''



from queue import PriorityQueue





def findMedian(arr, n):



    # To store the medians

    medians = []



    # max heap

    lo = PriorityQueue()



    # min heap

    hi = PriorityQueue()



    for i in range(n):



        num = arr[i]



        # Add to max heap

        lo.put(num)



        # Balancing step, that is inserting the current element at its position that is either less than median or more than median value

        temp = lo.get()

        # Inserting the val with negative priority because 'hi' is min heap

        hi.put((-temp, temp))



        # Maintain size property, as 'lo' can have utmost one more element than 'hi' or both have equal number of elements

        if (lo.qsize() < hi.qsize()):

            tempPair = hi.get()

            lo.put(tempPair[1])



        median = 0



        # For odd number of elements

        if(lo.qsize() > hi.qsize()):

            median = lo.queue[0]



        # For even number of elements

        else:

            median = (lo.queue[0] + hi.queue[0][1]) // 2



        medians.append(median)



    return medians

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 :

Input Format:

Output Format:

Note :

Constraints :

Top Amazon SDE-2 interview questions & answers

Popular interview questions of SDE-2

Top HR questions asked in Amazon SDE-2