Median is the middle element in the array (in sorted form).
The challange here is that we need to return the median in O(1) time.
- We can maintain a sortted array.? At each step sorting costs us nlog(n).
- We maintain 2 buckets of equal sizes. Left median contains all values less than a number
kand the right median contains all values greater than
In 2nd method the insertion will be complex (and not O(1)), but we can easily compute the median in O(1).
To distribute numbers in 2 buckets, we can use 2 heaps. Max_heap (left bucket) and Min_heap (right bucket).
If the current number is lesse than max in max_heap_left, we can insert in max_heap_left, other wise we can insert it in min_heap_right.
This may create uneven sizes of heap, so we need to check in each step if the sizes are uneven, if yes… we need to fix it.
Here is the implementation in Python.
Note: Max heap is not supported in Python, so I used min_heap and inserted (and popped elements) by multiying the number by -1.
import heapq def running_median(arr): max_heap_left =  min_heap_right =  for each in arr: if len(max_heap_left) == 0 or each len(min_heap_right): popped_number = max_heap_left * -1 heapq.heappop(max_heap_left) heapq.heappush(min_heap_right, popped_number ) else: popped_number = min_heap_right heapq.heappop(min_heap_right) heapq.heappush(max_heap_left, popped_number * -1) if len(max_heap_left) == len(min_heap_right): return (max_heap_left * -1 + min_heap_right)/2.0 else: if len(max_heap_left) > len(min_heap_right): return max_heap_left * -1 else: return min_heap_right arr = [1,2,3,4,5] print running_median(arr) arr = [1,2,3,4,5,6] print running_median(arr)