We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

I love the editorials for the opportunity to get new ideas on how to tackle a problem. I will study the two heap solution later.

My solution was to use a C++ std::map, which internally is a binary tree and does not invalidate iterators after an insert. (Some other commenters here mentioned something called sortedcontainers, which I think is the same idea.) The resulting complexity should be O(nlogn): logn for an insert in the binary tree, and this is done n times (once for each element in the input array). The idea is simple: keep a "(lower) median" iterator into the tree, and increment/decrement this iterator depending on whether a new value is added above or below the lower median. For an odd number of elements, lower median and median are the same, for even the median is the average of the lower median and the next element.

The tricky part is that, since numbers are allowed to repeat in the input array, one needs a bit of extra logic to keep track of "position" in bins associated to each input number. Code below. A bit ugly, but ya know, the best solution is the one you know and stuff.

## Find the Running Median

You are viewing a single comment's thread. Return to all comments â†’

I love the editorials for the opportunity to get new ideas on how to tackle a problem. I will study the two heap solution later.

My solution was to use a C++ std::map, which internally is a binary tree and does not invalidate iterators after an insert. (Some other commenters here mentioned something called sortedcontainers, which I think is the same idea.) The resulting complexity should be O(nlogn): logn for an insert in the binary tree, and this is done n times (once for each element in the input array). The idea is simple: keep a "(lower) median" iterator into the tree, and increment/decrement this iterator depending on whether a new value is added above or below the lower median. For an odd number of elements, lower median and median are the same, for even the median is the average of the lower median and the next element.

The tricky part is that, since numbers are allowed to repeat in the input array, one needs a bit of extra logic to keep track of "position" in bins associated to each input number. Code below. A bit ugly, but ya know, the best solution is the one you know and stuff.