Running Median
You are given a stream of 'N' integers. For every 'i-th' integer added to the running list of integers, print the resulting median.

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

Question

Running Median

You are given a stream of 'N' integers. For every 'i-th' integer added to the running list of integers, print the resulting median.

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

Accepted Answer

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.

Space Complexity: O(1)Explanation:

O(1).

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

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

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

Accepted Answer

Inserting At Correct Position

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.

Space Complexity: O(n)Explanation:

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

We maintain a list to support insertions that take O(N) Space Complexity. Hence, the overall Space Complexity is O(N).

Time Complexity: O(1)Explanation:

O(N ^ 2), where N is the number of elements in the array.

There are N additions, and each new addition takes O(N) time for insertion in the correct position. Hence, the overall Time Complexity is O(N ^ 2).

Accepted Answer

Min And Max Heap Approach

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.

Space Complexity: O(n)Explanation:

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

Maintaining the two heaps will require O(N) memory. Hence, the overall Space Complexity is O(N).

Time Complexity: O(nlogn)Explanation:

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

There are N additions, and each new addition takes O(log(N)) time for transition (insertion/deletion) of elements between the two heaps. Hence, the overall Time Complexity is O(N * log(N)).

You are given a stream of 'N' integers. For every 'i-th' integer added to the running list of integers, print the resulting median.

Print only the integer part of the median.

Input Format :

Output Format :

Input Constraints

Top Google Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Google Software Developer