Given an array as input find the output array that has median of each sub array whose index starts from 0 to i(i = 1,2...array.length-1)

Question

Given an array as input find the output array that has median of each sub array whose index starts from 0 to i(i = 1,2...array.length-1).

So basically given array A[], output array B[]. B[i] is the median of A[0] ... A[i].

I am thinking about using dynamic programming to store the two numbers before and after the median of each sub array. But it somehow gets complicated. Is there any easier solution?

Answer 1

Basically what we need here is a data structure that supports two operations: adding an arbitrary element and finding the median of all elements added to it so far.

1. The most conceptually simple solution is a balanced binary search tree that stores sizes of all subtrees(add operation just adds an element to the tree and finding median is just one traversal from the root of the tree(we can choose where to go in each node because we know the sizes of all subtrees). But this one might be a little bit tedious to implement(binary search trees from standard library usually don't support the "get k-th element" operation efficiently).

2. Here is another solution(it is O(N log N), too) which uses two heaps. It is easier implementation-wise because a priority queue from a standard library works fine.

   • Let's maintain two heaps: low(a max-heap) and high(a min-heap). The invariants are: any element of low are less than or equal to any element of high and their size differs by at most one.

   • Initially, they are empty.

   • When we add a new number, we do the following: if its less than or equal to the largest element in low, we add to low. Otherwise, we add to high. It is easy to see that the first invariant holds true. How to maintain the second invariant? If their sizes differ by 2 after insertion, we can just pop the top element from the larger heap and insert into the other one. Now their size differs by at most one. Thus, we can restore both invariants in O(log N) time when we add a new element.

   • These two invariants imply the following property: if size(low) != size(high), the median is the top element of the larger heap. If their sizes are equal, the median is the top of one them(which exactly? It depends on the definition of a median of an array with even number of elements).