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
  • Apply
  • 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 244 Discussions, By:

recency

Please Login in order to post a comment

  • mariano_tangari
    3 months ago+ 1 comment

    My short solution, passes all tests. Steps:

    1) Started sorting the input list.
    2) Iterated over the input list starting from the last element and decreasing the iterator. In each step of this loop, calculate the median of the sorted list and remove the last element of the non sorted original input list from the sorted list (using binary search to locate the element). 3) Reversed the result list.

    Code:

    public static List<Double> runningMedian(List<Integer> a) {

        var results = new ArrayList<Double>(); 
        var c = List.copyOf(a);
        Collections.sort(a);
    
        for (int k = a.size(); k > 0; k--) {
            if (k % 2 == 0) {
                results.add(((double) a.get(k / 2) + a.get((k / 2) - 1)) / 2.0);
            } else {
                results.add((double) a.get(k / 2));
            }
            a.remove(Collections.binarySearch(a, c.get(k - 1))); 
        }
        Collections.reverse(results); 
        return results; 
    }
    
    1|
    Permalink
  • fredydeltoro
    4 months ago+ 0 comments

    Hey this is my solution with Js

    function runningMedian(a) {
      let arr = a.map(el => el).sort((a, b) => a - b)
      let length = arr.length
      let isOdd = false
      let mid = []
      let half = length/2
      const result = []
      
      if(length % 2 !== 0){
        isOdd = true
        mid = [Math.ceil(half)-1]
      } else {
        mid = [(half - 1), half]
      }
          
      while(arr.length && a.length){
        let pop = arr.indexOf(a.pop())
        if(isOdd){
          result.unshift(arr[mid[0]])
          mid.unshift(mid[0]-1)
          arr.splice(pop, 1)
          isOdd = false
        } else{
          let media = (arr[mid[0]] + arr[mid[1]]) / 2
          result.unshift(media)
          mid.pop()
          arr.splice(pop, 1)
          isOdd = true
        }
      }
      
      return result
    }
    
    0|
    Permalink
  • nandeshboyz
    4 months ago+ 0 comments

    Hey There, Here is my C++ Solution using two heaps that passes all test case successfully*****

    void insert_increase(vector<int> &H,int x){
        H.push_back(x);
        int i=H.size()-1;
        while (i>0) {
            if(H[i]<H[(i-1)/2]) swap(H[i],H[(i-1)/2]);
            else break;
            i=(i-1)/2;
        }
    }
    void insert_decrease(vector<int> &H,int x){
        H.push_back(x);
        int i=H.size()-1;
        while (i>0) {
            if(H[i]>H[(i-1)/2]) swap(H[i],H[(i-1)/2]);
            else break;
            i=(i-1)/2;
        }
    }
    void update1(vector<int> &H,int x){
        H[0]=x;
        int i=0;
        int n=H.size()-1;
        while (2*i+1<=n) {
            int max=i;
            if(H[2*i+1]>H[i]) max=2*i+1;
            if((2*i+2<=n)&(H[2*i+2]>H[max])) max=2*i+2;
            if(max!=i){
                swap(H[i],H[max]);
                i=max;
            }
            else break;
        }
    }
    void update2(vector<int> &H,int x){
        H[0]=x;
        int i=0;
        int n=H.size()-1;
        while (2*i+1<=n) {
            int min=i;
            if(H[2*i+1]<H[i]) min=2*i+1;
            if((2*i+2<=n)&(H[2*i+2]<H[min])) min=2*i+2;
            if(min!=i){
                swap(H[i],H[min]);
                i=min;
            }
            else break;
        }
    }
    vector<double> runningMedian(vector<int> a) {
        vector<int>H1;
        vector<int>H2;
        vector<double> v;
        v.push_back(a[0]);
        insert_decrease(H1,a[0]);
        for(int i=1;i<a.size();i++){
            if(i%2==0) insert_decrease(H1,a[i]);
            else insert_increase(H2,a[i]);
            
            if(H1[0]>H2[0]) {
                int temp=H1[0];
                update1(H1,H2[0]);
                update2(H2,temp);
            }
            if(i%2==0)v.push_back(double(H1[0]));
            else v.push_back(double((H1[0]+H2[0])/2.0));
        }
        return v;
    }
    
    return v;
    

    }

    0|
    Permalink
  • rob_stemmler
    5 months ago+ 0 comments

    Python3 solution, passes all test cases. With explanation!

    import heapq
    
    # We're going to split the list into "low" and "high" halves.
    
    # The high half will be a MIN heap, the low half will be a MAX heap.
    # We'll pop one into the other as needed to keep them close in size.
    
    # Then low[0] & high[0] will always return middle values of the list.
    
    # In order to implement a max heap with heapq, we just fill it with
    # negative numbers. So we'll invert numbers we push into low, and
    # re-invert numbers we pop out of it.
    
    def runningMedian(a):
        low = []    # Lower half of the input
        high = []   # Upper half of the input
        ans = []    # List of median values
    
        for i in range(len(a)):
            # First, sort the list value into the correct half.
            # We'll prioritize high to minimize negative inversion.
    
            if i == 0 or a[i] >= med:
                heapq.heappush(high, a[i])
            else:
                heapq.heappush(low, a[i] * -1)
    
            # Now make sure the halves are equally sized. Since high
            # is filled first, it can be one element longer than low.
            # Otherwise they must have equal lengths.
    
            if len(high) - len(low) > 1:
                heapq.heappush(low, heapq.heappop(high) * -1)
            elif len(low) > len(high):
                heapq.heappush(high, heapq.heappop(low) * -1)
    
            # Rest of the logic is easy. If high is longer than low,
            # there's an odd number of elements in the list, and the
            # middle value is the bottom of high. Otherwise, there's
            # an even number of elements in the list, so the median
            # is half the sum of each half's 0th element. Since low is
            # stored negative, we'll just subtract it to find the sum.
    
            if len(high) > len(low):
                med = float(high[0])
            else:
                med = float((high[0] - low[0]) / 2)
    
            ans.append(med)
    
        return ans
    
    0|
    Permalink
  • lord_tejas
    6 months ago+ 0 comments

    My python3 O (n * log n) solution. for beginners

    def get_median(arr):
        
        # Must pass sorted array
        n = len(arr)
        
        if n == 1: return arr[0]
    
        if n % 2 == 0:
            return round((arr[n // 2] + arr[n // 2 - 1]) / 2, 1)
        
        return round(arr[n // 2], 1)
    
    
    def get_min_index(arr, x):
        """
        Fetch Min Index
        """
        
        # index = 0
        n = len(arr)
        
        # Optimisation
        
        # Base Checks
        if n == 0: return 0
        if x <= arr[0]: return 0
        if x >= arr[n-1]: return n
        
        l = 0
        r = n - 1
        
        while l < r:
            
            mid = (l + r) >> 1
            
            if arr[mid] < x: l = mid + 1
            else: r = mid
        
        return l
    
        
    def sorted_insert(arr, x):
        min_index = get_min_index(arr, x)
        
        # Insert element
        arr.insert(min_index, x)
    
    def runningMedian(a):
        # Write your code here
        
        sorted_arr = []
        running_median = []
        
        for ele in a: # O(n) * log n time 
            sorted_insert(sorted_arr, ele) # O(log n) time avg~
            running_median.append(get_median(sorted_arr))
            
        return running_median
    
    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