295: Time 97.64%, Solution with step by step explanation
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\nThe MedianFinder class maintains two heaps: self.small (a max heap) and s
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nThe MedianFinder class maintains two heaps: self.small (a max heap) and self.large (a min heap). The median is either the largest element in self.small, the smallest element in self.large, or the average of these two elements if the heaps have the same size.\n\nThe addNum method first pushes the new element onto self.small. If self.small becomes larger than self.large, the largest element in self.small is popped and pushed onto self.large. If self.large becomes larger than self.small, the smallest element in self.large is popped and pushed onto self.small.\n\nThe findMedian method returns the median as described above.\n\n# Complexity\n- Time complexity:\n97.64%\n\n- Space complexity:\n79.57%\n\n# Code\n```\nimport heapq\n\nclass MedianFinder:\n    def __init__(self):\n        """\n        initialize your data structure here.\n        """\n        self.small = []\n        self.large = []\n\n    def addNum(self, num: int) -> None:\n        if len(self.small) == len(self.large):\n            heapq.heappush(self.large, -heapq.heappushpop(self.small, -num))\n        else:\n            heapq.heappush(self.small, -heapq.heappushpop(self.large, num))\n\n    def findMedian(self) -> float:\n        if len(self.small) == len(self.large):\n            return (self.large[0] - self.small[0]) / 2.0\n        else:\n            return float(self.large[0])\n\n```
['Two Pointers', 'Design', 'Heap (Priority Queue)', 'Python', 'Python3']