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.
  • HackerRank Home

    HackerRank

  • |
  • Prepare
  • Certify
  • Compete
  • Hiring developers?
  1. Prepare
  2. Data Structures
  3. Heap
  4. Find the Running Median
  5. Discussions

Find the Running Median

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 239 Discussions, By:

recency

Please Login in order to post a comment

  • hassanfathi2002
    2 weeks ago+ 0 comments

    for c++ , all you need is this :

    #include <ext/pb_ds/assoc_container.hpp>
    using namespace __gnu_pbds;
    typedef tree<int,null_type,less_equal<dbl>,rb_tree_tag,
    tree_order_statistics_node_update> indexed_set;
    
    -1|
    Permalink
  • eduardo_angel124
    4 months ago+ 0 comments

    this my solution but after the 2 case not working with more data :c help

    def runningMedian(a):
        # Write your code here
        res = []
        temp = []
        count =  0
        for number in a:
            temp.append(number)
            temp = sorted(temp)
            size  = len(temp)
            middle =  round(size / 2)
            impar = (size % 2)
    
            if(impar == 1):
                currentSize =  size -1 
                middleImpar =  round(currentSize / 2)
                median = temp[middleImpar]
                res.append(float(median))
            else:
                median =  (temp[middle -1] + temp[middle]) / 2
                res.append(float(median))
                
        return res
    
    0|
    Permalink
  • meganwang2012
    5 months ago+ 1 comment
        public static PriorityQueue<int, int> MinHeap = new PriorityQueue<int, int>();
    
        public static PriorityQueue<int, int> MaxHeap = new PriorityQueue<int, int>(new IMaxCompareTo() );
    
        public static List<string> runningMedian(List<int> inputData)
        {       
    
            double median = 0;
            List<string> medians = new List<string>();            
    
            for (int i = 0; i < inputData.Count; i++)
            {    
                int currentValue = inputData[i];
    
                if (MaxHeap.Count == 0 || currentValue <= MaxHeap.Peek())
                {
    
                    MaxHeap.Enqueue(currentValue, currentValue);
                }
                else { 
    
                    MinHeap.Enqueue(currentValue, currentValue);
                }
    
    
                if ((MinHeap.Count - MaxHeap.Count) >= 2) {
    
                    MaxHeap.Enqueue(MinHeap.Peek(), MinHeap.Peek());
                    MinHeap.Dequeue();
                }
    
                else if ((MaxHeap.Count-MinHeap.Count)>=2) {
    
                    MinHeap.Enqueue(MaxHeap.Peek(), MaxHeap.Peek());
                    MaxHeap.Dequeue();
    
                }
    
                if (MinHeap.Count == MaxHeap.Count)
                {
    
                    median = (double)(MinHeap.Peek() + MaxHeap.Peek()) / 2;
                }
                else if (MinHeap.Count > MaxHeap.Count)
                {
    
                    median = MinHeap.Peek();
                }
                else {
    
                    median = MaxHeap.Peek();
    
                }
    
                var stringM = median.ToString("0.0");
                medians.Add(stringM);
    
            }
    
            return medians;
    
        }
    
    
    
        public class IMaxCompareTo: IComparer<int>
    
        {
            public int Compare(int x, int y) => y.CompareTo(x);
        }
    
    0|
    Permalink
  • abhaynayak24
    5 months ago+ 0 comments

    Python Interview appropriate heap solution addNum: O(log N) findMedian: O(1) Total = O (log N)

    from heapq import heappush, heappop
    class Median:
        def __init__(self):
            self.maxHeap, self.minHeap = [], []
        
        def addNum(self, num):
            heappush(self.maxHeap, -num)
            
            if self.minHeap and self.maxHeap and -self.maxHeap[0] > self.minHeap[0]:
                heappush(self.minHeap, -heappop(self.maxHeap))
            
            if len(self.minHeap) > len(self.maxHeap) + 1:
                heappush(self.maxHeap, -heappop(self.minHeap))
            
            if len(self.maxHeap) > len(self.minHeap) + 1:
                heappush(self.minHeap, -heappop(self.maxHeap))
                
        def findMedian(self):
            if len(self.maxHeap) > len(self.minHeap):
                return float(-self.maxHeap[0])
            
            if len(self.maxHeap) < len(self.minHeap):
                return float(self.minHeap[0])
            else:
                return (self.minHeap[0] - self.maxHeap[0]) / 2
            
    def runningMedian(a):
        obj = Median()
        result = list()
        for i in a:
            obj.addNum(i)
            result.append(obj.findMedian())
        return result
    
    0|
    Permalink
  • pmtatar
    5 months ago+ 0 comments
    def calculate_median(a):
        mid1 = a[len(a) // 2]
        mid2 = a[(len(a) - 1) // 2]
        return (mid1 + mid2) / 2
    
    def sort_insert(arr, num):
        if not arr:
            arr.append(num)
            return
    
        start = 0
        end = len(arr) -1
        while start < end:
            mid = (end + start) // 2
            if arr[mid] < num:
                start = mid + 1
            elif arr[mid] >= num:
                end = mid - 1
        else:
            if num < arr[start]:
                arr.insert(start, num)
            else:
                arr.insert(start+1, num)
     
    def runningMedian(a):
        arr = []
        result = []
        for i in range(len(a)):
            sort_insert(arr, a[i])
            result.append(calculate_median(arr))
        return result
    
    0|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy