Discussion on Find the Running Median Challenge

Sort by

recency

|

252 Discussions

|

3 months ago+ 0 comments

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)

3 months ago+ 0 comments

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;

5 months ago+ 0 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.

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;
}

6 months ago+ 0 comments

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;
}

9 months ago+ 0 comments

My Python solution using two heaps.

def runningMedian(a):
    # Declaring two min heap
		# import at the top
		# from heapq import heappush, heappop, heapify
    
    g = []
    s = []
    result = []
    for i in range(len(a)):
       
        # Negation for treating it as max heap
        heappush(s, -a[i])
        heappush(g, -heappop(s))
        if len(g) > len(s):
            heappush(s, -heappop(g))
 
        if len(g) != len(s):
            result.append(float(-s[0]))
        else:
            result.append(float((g[0] - s[0])/2))
        
    return result