Single Multiset | Track the median using iterator | C++/Java/Python
Intuition
We use a multiset to automatically keep the numbers sorted as they are added.
By maintaining an iterator (mid) that points to the middle element, we c
# Intuition
- We use a multiset to automatically keep the numbers sorted as they are added. 
- By maintaining an iterator (mid) that points to the middle element, we can efficiently track the median

# Approach
**Step-by-Step Explanation:**
1. **Adding a Number**: addNum(int num)
    - When adding a new number, we want to ensure that the mid iterator always points to the current middle of the list.
    - **First number**:
        - If this is the first number, we simply insert it into the multiset, and set mid to point to this first element.
    - **Subsequent numbers**:
        - Insert the number into the multiset, which keeps the collection sorted.
        - Depending on whether the number of elements is odd or even, we need to adjust the mid iterator:
            - Odd-sized collection: The mid iterator points directly to the middle element.
            - Even-sized collection: The mid iterator will need to move either left or right to balance the middle two elements.
        - **Balancing the middle**:
            - If the new number is smaller than the current mid value, we shift the mid pointer left.
            - If the new number is greater than or equal to the current mid value, we shift the mid pointer right.
2. **Finding the Median**: findMedian()
    - If the collection has an odd size: The mid iterator points directly to the middle element. We simply return this element as the median.
    - If the collection has an even size: The median is the average of the two middle elements. The mid iterator points to one of these middle elements, and we can easily find the second middle element by incrementing the mid iterator.

# Complexity
- **Time complexity:**
    - **addNum(int num)**: Inserting into a multiset takes `O(logn)`, where n is the number of elements in the set. The adjustment of mid is `O(1)`.
    - **findMedian()**: Finding the median is `O(1)` because we simply return the value pointed to by mid (or the average of two middle elements).

- **Space complexity**:
    - `O(n)` where n is the number of elements, as we are storing all elements in the multiset.

# Code
```cpp []
class MedianFinder {
public:
    // Multiset to store the numbers in sorted order
    multiset<int> S;  
    // Iterator to track the middle element
    multiset<int>::iterator mid;  

    MedianFinder() {
    }
    
    void addNum(int num) {
        // Initalize `mid` in case of first element
        if(S.size() == 0) {
            S.insert(num);
            mid = S.begin();
        } 
        else {
            // Insert the number into the multiset
            S.insert(num);  
            
            // Adjust the 'mid' iterator to point to the middle element
            if(S.size() % 2 == 0) {
                if(num < *mid) 
                    mid--;
            } 
            else {
                if(num >= *mid) 
                    mid++;
            }
        }
    }
    
    double findMedian() {
        if(S.size() % 2 == 0) {
            // If the size is even, return the average of the two middle elements
            auto midP = mid; 
            midP++;  // Move to the second middle element
            return (double)(*mid + *midP) / 2;
        } 
        else {
            // If the size is odd, return the middle element
            return *mid;
        }
    }
};
```
['Python', 'C++', 'Java']