Problem statement

https://binarysearch.com/problems/Rolling-Median/

Solution

Equal to Leetcode 0295. Find Median from Data Stream.

Complexity

Time complexity is just O(1) to get median and O(log n) to add number. Space complexity is O(n) after n operations.

Code

class RollingMedian:
    def __init__(self):
        self.small, self.large = [], [] 

    def add(self, num):
        heappush(self.small, -num)           
        heappush(self.large, -heappop(self.small))
        
        if len(self.small) < len(self.large):
            heappush(self.small, -heappop(self.large))
            
    def median(self):
        if len(self.large) != len(self.small):
            return -self.small[0]                  
        else:
            return (self.large[0] - self.small[0]) / 2