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
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • 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

    You are viewing a single comment's thread. Return to all comments →

  • meganwang2012
    3 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
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy