I am surprised that I was able to get away with using a simple list structure (vector in C++). I started off with a simple, slow solution using std::sort, and then when that didn't pass, I made sure to insert each incoming int in the correct location. That was it. Not hard.

Python3

import heapq import sys

def runningMedian(a):

lower_half = []   
upper_half = []   

result = []

for num in a:

    if len(lower_half) == 0 or num <= -lower_half[0]:
        heapq.heappush(lower_half, -num)  
    else:
        heapq.heappush(upper_half, num)


    if len(lower_half) > len(upper_half) + 1:
        moved_item = -heapq.heappop(lower_half)
        heapq.heappush(upper_half, moved_item)
    elif len(upper_half) > len(lower_half):
        moved_item = heapq.heappop(upper_half)
        heapq.heappush(lower_half, -moved_item)

    if len(lower_half) == len(upper_half):
        median = (-lower_half[0] + upper_half[0]) / 2.0
    else:
        median = -lower_half[0] / 1.0  


    result.append(format(median, ".1f"))

return result

if name == "main": input = sys.stdin.read().strip().split() n = int(input[0]) a = list(map(int, input[1:n+1])) medians = runningMedian(a) for median in medians: print(median)

c++ solution, i also modified this line: for (size_t i = 0; i < result.size(); i++) { cout << std::fixed << std::setprecision(1) << result[i]; if (i != result.size() - 1) { cout << "\n"; } }

vector<double> runningMedian(vector<int> a) {
vector<int> sortedvec;
vector<double>result;
sortedvec.reserve(a.size());
result.reserve(a.size());
sortedvec.push_back(a[0]);
double d = a[0] * 1.0;
result.push_back(d);
int N = sortedvec.size();
for (int i = 1; i < a.size(); ++i) {
    auto index = upper_bound(sortedvec.begin(), sortedvec.end(), a[i]);
    sortedvec.insert(index, a[i]);
    N = sortedvec.size();
    double median;
    if (N % 2 == 0) {
        int mid = N / 2;
        median = (sortedvec[mid] + sortedvec[mid - 1]) / 2.0;
    }
    else {
        median = sortedvec[N / 2] * 1.0;
    }
    result.push_back(median);
		
}
return result;

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.

c++
vector<double> runningMedian(vector<int> const&a) {
    if(0==a.size())
        return vector<double>();
    map<int,int> aux; 
    aux.insert({a[0],1});
    auto lowerMed = aux.begin();
    vector<double> retq;
    retq.push_back(1.0*(lowerMed->first));
    int pos=0;
    for(int i=1; i<a.size();i++)
    {
        if(!aux.count(a[i]))
            aux.insert({a[i],1});
        else{aux[a[i]]++;}
        if((a[i]<lowerMed->first)&&(i&1))
            pos--;
        else if((a[i]>=lowerMed->first)&&(0==(i&1)))
            pos++;
        if(0>pos)
        {
            lowerMed--;
            pos=lowerMed->second-1;
        }
        else if(lowerMed->second<=pos)
        {
            lowerMed++;
            pos=0;
        }
        if(0==(i&1))
        {
            retq.push_back(1.0*(lowerMed->first));
        }
        else
        {
            auto x=lowerMed;
            if(pos+1>=lowerMed->second)
                x++; 
            retq.push_back(0.5*(lowerMed->first + x->first));
        }
    }
    return retq;
}

This is my c++ code, it passed but is it good enough?

vector<double> runningMedian(vector<int> a)
{
  vector<int> tmpArr;
  for (int i : a)
    tmpArr.push_back(i);

  sort(tmpArr.begin(), tmpArr.end());
  reverse(a.begin(), a.end());

  vector<double> re;
  for (int i : a)
  {
    int mid = (tmpArr.size() - 1) / 2;
    double sum = tmpArr.at(mid);
    if (tmpArr.size() % 2 == 0)
    {
      sum += tmpArr.at(mid + 1);
      sum /= 2;
    }
    re.insert(re.begin(), sum);

    auto idx = find(tmpArr.begin(), tmpArr.end(), i);
    tmpArr.erase(idx);
  }

  return re;
}