BackhardHeap

Running Median Calculation Solution

Problem Statement

Design a data structure to efficiently calculate the running median of a sequence of integers. The sequence is presented as a stream, where each integer is added one at a time. For an even number of elements, the median should be the average of the two middle elements.

Example 1
Input
[1, 3, 5, 2, 4]
Output
[1, 2, 3, 2.5, 3]
Example 2
Input
[10, 20, 30, 40, 50]
Output
[10, 15, 20, 25, 30]

Constraints

  • All integers in the stream are between 1 and 10^5
  • The stream can contain up to 10^4 integers
  • The data structure should use a maximum of O(n) extra space, where n is the number of integers in the stream
  • The time complexity of adding an integer and calculating the median should be O(log n)

More Heap Problems

Segmented Interval PartitioneasySegmented Subsequence SumeasySegmented Node ClustereasySegmented Capacity Windoweasy
View all problems →
Live Compiler
Loading...
Test Cases & Output
🔒 Sign up to run your code

🚀 Practice this problem

Run code, get AI hints & track streak

Sign Up Free