[link](https://leetcode.com/problems/find-median-from-data-stream/)

---

The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value, and the median is the mean of the two middle values.

For example, for arr = [2,3,4], the median is 3.
For example, for arr = [2,3], the median is (2 + 3) / 2 = 2.5.
Implement the MedianFinder class:

MedianFinder() initializes the MedianFinder object.
void addNum(int num) adds the integer num from the data stream to the data structure.
double findMedian() returns the median of all elements so far. Answers within 10-5 of the actual answer will be accepted.

#### Example 1:

Input
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
Output
[null, null, null, 1.5, null, 2.0]

Explanation
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

#### Constraints:

- -105 <= num <= 105
- There will be at least one element in the data structure before calling findMedian.
- At most 5 * 104 calls will be made to addNum and findMedian.

Follow up:

- If all integer numbers from the stream are in the range [0, 100], how would you optimize your solution?
- If 99% of all integer numbers from the stream are in the range [0, 100], how would you optimize your solution?

---

small: This is a max-heap (implemented as a min-heap with negated values) that stores the smaller half of the elements. The top of the heap represents the largest element in the smaller half.

large: This is a min-heap that stores the larger half of the elements. The top of the heap represents the smallest element in the larger half.

The constructor initializes both heaps as empty. The addNum method is used to add a new integer to the stream. It performs the following steps:

Push the negated value of the given integer into the small max-heap. If the small max-heap is not empty and the top element of small is greater than the top element of large, it means that the order of elements in the two heaps is not correct. So, pop the top element from small, negate it, and push it into the large min-heap. This step ensures that small contains the smaller half and large contains the larger half of the elements.

If the size of small is greater than the size of large plus 1 (uneven size), pop the top element from small, negate it, and push it into large. This step ensures that the difference in the sizes of the two heaps is at most 1, which is necessary to calculate the median later.

If the size of large is greater than the size of small plus 1 (uneven size), pop the top element from large, negate it, and push it into small. Again, this step maintains the condition of having the difference in sizes at most 1.

The findMedian method is used to compute the median. If the sizes of both heaps are equal, the median is the average of the top elements of both heaps. Otherwise, the median is the top element of the heap with the larger size.

#### Solution 1

class MedianFinder:

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

    def addNum(self, num: int) -> None:
        heapq.heappush(self.small, -1 * num)
        if (self.small and self.large and (-1 * self.small[0]) > self.large[0]):
            val = -1 * heapq.heappop(self.small)
            heapq.heappush(self.large, val)

        # Handle uneven size
        if len(self.small) > len(self.large) + 1:
            val = -1 * heapq.heappop(self.small)
            heapq.heappush(self.large, val)
        
        elif len(self.large) > len(self.small) + 1:
            val = heapq.heappop(self.large)
            heapq.heappush(self.small, -1 * val)

        
    def findMedian(self) -> float:
        if len(self.small) > len(self.large):
            return (-1 * self.small[0])
        elif len(self.large) > len(self.small):
            return self.large[0]
        
        return (((-1 * self.small[0]) + self.large[0]) / 2)
        

The time complexity of the addNum method is O(log n) for each addition, where n is the number of elements in the heaps. The findMedian method has a constant time complexity of O(1) since it only involves accessing the top elements of the heaps.

The space complexity is O(n), where n is the number of elements stored in the heaps.