Tuesday, October 18, 2011

Compute the running median and the running average

You are given a very long stream and you need to compute the running median for each group of 1k numbers. Same question for the running median. What is the complexity?

Suppose you know a priori the number of elements in the stream.

given a running average, you can update the group by adding a new element and removing the oldest one. This will give you a solution that is linear in the number of elements in the stream

Similar intuition is for the median, you can use a balanced BST where every node has the number of nodes contained in the subtree rooted at it.


  1. BST would be costly to consider due to balancing.

    Rather we can make use of one median element and two heaps, a MinHeap and a MaxHeap. As the elements from stream are read, push the median to appropriate heap and update the median with balanced element.

  2. We published a sample implementation of above approach http://www.geeksforgeeks.org/archives/14873