Running Median Problem

Given a stream of integers, calculate and print the median after each new integer is added to the stream.

Output only the integer part of the median.

Example:

Input:

N = 5
Stream = [2, 3, 4, 1, 6]

Output:

2 2 3 2 3

Constraints:

0 ≤ N ≤ 10^5

1 ≤ ARR[i] ≤ 10^5

Time Limit: 1 sec

Question

Given a stream of integers, calculate and print the median after each new integer is added to the stream.

Output only the integer part of the median.

N = 5  
Stream = [2, 3, 4, 1, 6]

2 2 3 2 3

Accepted Answer

Calculate and print the median after each new integer is added to a stream of integers.

Use a min heap to store the larger half of the numbers and a max heap to store the smaller half.
Keep the sizes of the two heaps balanced to efficiently calculate the median.
If the total number of elements is odd, the median is the top element of the max heap.
If the total number of elements is even, the median is the average of the top elements of both heaps.

Amazon Software Developer Intern interview questions & answers