69.1 (Approach 1) | O( log n)✅ | Python & C++(Step by step explanation)✅
Intuition\nThe problem requires finding the median of a stream of integers efficiently. To achieve this, we can use two heaps: a max heap to store the smaller h
# Intuition\nThe problem requires finding the median of a stream of integers efficiently. To achieve this, we can use two heaps: a max heap to store the smaller half of the numbers and a min heap to store the larger half. By maintaining these heaps such that the sizes are balanced or differ by at most one, we can easily find the median.\n\n# Approach\n- Initialize two heaps: `small` to store the smaller half of the numbers as a max heap and `large` to store the larger half of the numbers as a min heap.\n- When adding a new number:\n  - If the number is greater than the smallest number in the `large` heap, push it to the `large` heap.\n  - Otherwise, push the negation of the number to the `small` heap.\n  - Balance the heaps by adjusting their sizes if necessary:\n    - If the size of the `small` heap becomes greater than the size of the `large` heap by more than one, pop the maximum element from the `small` heap and push it to the `large` heap.\n    - If the size of the `large` heap becomes greater than the size of the `small` heap by more than one, pop the minimum element from the `large` heap and push its negation to the `small` heap.\n- To find the median:\n  - If the sizes of the heaps are equal, the median is the average of the maximum element in the `small` heap and the minimum element in the `large` heap.\n  - Otherwise, the median is the maximum element in the `small` heap if its size is greater, or the minimum element in the `large` heap if its size is greater.\n\n# Complexity\n- Time complexity:\n  - Adding a number takes O(log n) time, where n is the number of elements in the heaps.\n  - Finding the median takes O(1) time.\n- Space complexity:\n  - The space complexity is O(n), where n is the number of elements stored in the heaps.\n\n\n## Python Implementation:\n```python\nclass MedianFinder:\n    def __init__(self):\n        """\n        initialize your data structure here.\n        """\n        # Initialize two heaps: small to store the smaller half as a max heap\n        # and large to store the larger half as a min heap\n        self.small, self.large = [], []\n\n    def addNum(self, num: int) -> None:\n        # If large heap is not empty and the number is greater than the smallest number in large heap,\n        # push it to the large heap. Otherwise, push the negation of the number to the small heap.\n        if self.large and num > self.large[0]:\n            heapq.heappush(self.large, num)\n        else:\n            heapq.heappush(self.small, -1 * num)\n\n        # Balance the heaps by adjusting their sizes if necessary\n        if len(self.small) > len(self.large) + 1:\n            val = -1 * heapq.heappop(self.small)\n            heapq.heappush(self.large, val)\n        if len(self.large) > len(self.small) + 1:\n            val = heapq.heappop(self.large)\n            heapq.heappush(self.small, -1 * val)\n\n    def findMedian(self) -> float:\n        # If sizes of both heaps are equal, return the average of the maximum element in the small heap\n        # and the minimum element in the large heap\n        if len(self.small) > len(self.large):\n            return -1 * self.small[0]\n        elif len(self.large) > len(self.small):\n            return self.large[0]\n        return (-1 * self.small[0] + self.large[0]) / 2.0\n```\n\n## C++ Implementation:\n```c++\nclass MedianFinder {\npublic:\n    MedianFinder() {\n        \n    }\n    \n    void addNum(int num) {\n        if (lower.empty()) {\n            // If lower heap is empty, push the number directly to it\n            lower.push(num);\n            return;\n        }\n        \n        if (lower.size() > higher.size()) {\n            if (lower.top() > num) {\n                // If lower heap size is greater than higher heap size and the number is less than the\n                // top element of the lower heap, push it to the higher heap after swapping the top\n                // element of the lower heap with the number\n                higher.push(lower.top());\n                lower.pop();\n                lower.push(num);\n            } else {\n                // If the number is greater than or equal to the top element of the lower heap,\n                // push it directly to the higher heap\n                higher.push(num);\n            }\n        } else {\n            if (num > higher.top()) {\n                // If higher heap size is greater than or equal to lower heap size and the number is\n                // greater than the top element of the higher heap, push it to the lower heap after\n                // swapping the top element of the higher heap with the number\n                lower.push(higher.top());\n                higher.pop();\n                higher.push(num);\n            } else {\n                // If the number is less than or equal to the top element of the higher heap,\n                // push it directly to the lower heap\n                lower.push(num);\n            }\n        }\n    }\n    \n    double findMedian() {\n        double result = 0.0;\n        \n        if (lower.size() == higher.size()) {\n            // If both heaps are of equal size, return the average of their top elements\n            result = lower.top() + (higher.top() - lower.top()) / 2.0;\n        } else {\n            // If lower heap size is greater than higher heap size, return the top element of the lower heap\n            // Otherwise, return the top element of the higher heap\n            result = (lower.size() > higher.size()) ? lower.top() : higher.top();\n        }\n        \n        return result;\n    }\nprivate:\n    priority_queue<int> lower;  // Max heap\n    priority_queue<int, vector<int>, greater<int>> higher;  // Min heap\n};\n```\n\n# Please upvote the solution if you understood it.\n![1_3vhNKl1AW3wdbkTshO9ryQ.jpg](https://assets.leetcode.com/users/images/0161dd3b-ad9f-4cf6-8c43-49c2e670cc21_1699210823.334661.jpeg)\n
['Design', 'Heap (Priority Queue)', 'Data Stream', 'C++', 'Python3']