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.
  1. Prepare
  2. Data Structures
  3. Heap
  4. Find the Running Median
  5. Discussions

Find the Running Median

Sort by

recency

|

257 Discussions

|

  • safee7
     + 0 comments

    Easy C++ Solution using Heaps in O(nlog(n)) Time Complexity.

    vector<double> runningMedian(vector<int>& a) {
    priority_queue<int> maxHeap; // smaller half
    priority_queue<int, vector<int>, greater<int>> minHeap; // larger half
    vector<double> ans;

    for (int num : a) {
        maxHeap.push(num);

        // Move largest of smaller half to min heap
        int temp = maxHeap.top();
        maxHeap.pop();
        minHeap.push(temp);

        // Balance heaps sizes
        if (minHeap.size() > maxHeap.size()) {
            temp = minHeap.top();
            minHeap.pop();
            maxHeap.push(temp);
        }

        // Calculate median
        double median;
        if (maxHeap.size() != minHeap.size()) {
            median = maxHeap.top();
        } else {
            median = (maxHeap.top() + minHeap.top()) / 2.0;
        }

        // Round to 1 decimal place
        median = round(median * 10.0) / 10.0;

        ans.push_back(median);
    }

    return ans;
}

  • CS_2212256_T
     + 0 comments
    import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static class MinComparator implements Comparator<Integer> {
        @Override
        public int compare(Integer i1, Integer i2) {
            if (i1 < i2) {
                return -1;
            } else if (i1 > i2) {
                return 1;
            } else {
                return 0;
            }
        }
    }

    public static class MaxComparator implements Comparator<Integer> {
        @Override
        public int compare(Integer i1, Integer i2) {
            if (i1 > i2) {
                return -1;
            } else if (i1 < i2) {
                return 1;
            } else {
                return 0;
            }
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();

        Queue<Integer> minHeap = new PriorityQueue<>(n/2+1, new MinComparator());
        Queue<Integer> maxHeap = new PriorityQueue<>(n/2+1, new MaxComparator());

        for (int i = 0; i < n; i++) {
            int num = in.nextInt();

            if (!maxHeap.isEmpty() && num > maxHeap.peek()) {
                minHeap.offer(num);
            } else {
                maxHeap.offer(num);
            }

            if (minHeap.size() > maxHeap.size() + 1) {
                maxHeap.offer(minHeap.poll());
            } else if (maxHeap.size() > minHeap.size() + 1) {
                minHeap.offer(maxHeap.poll());
            }

            double median = 0.0;
            if (minHeap.size() == maxHeap.size()) {
                median = 0.5 * (minHeap.peek() + maxHeap.peek());
            } else {
                median = (minHeap.size() > maxHeap.size()) ? minHeap.peek() : maxHeap.peek();
            }

            System.out.println(String.format("%1.1f", median));
        }
    }

}

  • 2k23_cscys_23101
     + 0 comments

    import math import os import random import re import sys

    def runningMedian(a):

    if name == 'main': fptr = open(os.environ['OUTPUT_PATH'], 'w')

    a_count = int(input().strip())

a = []

for _ in range(a_count):
    a_item = int(input().strip())
    a.append(a_item)

result = runningMedian(a)

fptr.write('\n'.join(map(str, result)))
fptr.write('\n')

fptr.close()

  • manceraaxel
     + 0 comments
    import heapq

def runningMedian(a):
    maxh = []
    minh = []
    ans = []

    for aa in a:
        if len(maxh) == 0 or aa <= -maxh[0]:
            heapq.heappush(maxh, -aa)
        else:
            heapq.heappush(minh, aa)

        if len(maxh) > len(minh) + 1:
            heapq.heappush(minh, -heapq.heappop(maxh))
        elif len(minh) > len(maxh):
            heapq.heappush(maxh, -heapq.heappop(minh))

        if len(maxh) > len(minh):
            m = -maxh[0]
        else:
            m = (-maxh[0] + minh[0]) / 2
        ans.append(format(m, ".1f"))

    return ans

  • bahlquist
     + 0 comments

    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.