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 →

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