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 →

  • eghc4nxohb3p
    4 years ago+ 1 comment

    This follows Gayle Laakmann McDowell's approach published by HackerRank (see here) but in Python 3:

    import heapq
    
    def addNum(num, lowers, highers):
        if not lowers or num < -lowers[0]:
            heapq.heappush(lowers,-num)
        else:
            heapq.heappush(highers,num)
        
    def rebalance(lowers, highers):
        if len(lowers) - len(highers) >= 2:
            heapq.heappush(highers,-heapq.heappop(lowers))
        elif len(highers) - len(lowers) >= 2:
            heapq.heappush(lowers,-heapq.heappop(highers))
    
    def getMedian(lowers, highers):
        if len(lowers) == len(highers):
            return (-lowers[0] + highers[0])/2
        if len(lowers) > len(highers):
            return float(-lowers[0])
        else:
            return float(highers[0])
    
    
    def runningMedian(a):
        lowers = []  # max heap, vals should go in and come out negated
        highers = []  # min heap, vals should go in positive
        result = []
        for v in a:
            addNum(v, lowers, highers)
            rebalance(lowers, highers)
            result.append(round(getMedian(lowers, highers),1))
        return result
    

    Unfortunately, the heapq module is not object-oriented, only implements a min-heap discipline, and does not provide the ability to use a custom comparator, which would make this way easier with regard to the max-heap.

    12|
    Permalink
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature