Intuitive Solution + Approach : 2 Heaps ✅
Intuition\nBuild the intuition to this problem starting with a simple array and observe how we are not concerned by all the elements of the array, but just the 
# Intuition\nBuild the intuition to this problem starting with a simple array and observe how we are not concerned by all the elements of the array, but just the ones in the middle (while all the elements are sorted). \n\nWe can keep pushing elements again and again using the addNum function and keep sorting the array after every insertion. But that would be a costly approach and would lead to TLE considering the constraints of this problem. \n\nSo, we break the array into two parts, where we need the largest element of the first array and the smallest element of the second array to calculate the median (in case of even number of elements). This is how we can draw intuition to use 2 heaps : `maxHeap` to return the largest value in the first half and `minHeap` to return the minimum value in the second half. \n\n# Approach\n\n1. **Insert Element into maxHeap**: Push every new element to the maxHeap. This ensures that the largest element in the maxHeap is always at the top.\n2. **Balance Heaps**: After inserting into maxHeap, we need to ensure that all values in maxHeap are smaller than those in minHeap. So, if `maxHeap.top() > minHeap.top()`, move the top element of maxHeap to minHeap.\n3. **Size Balancing**: Ensure that the size difference between the two heaps is no more than 1:\n    - If maxHeap has more than one extra element compared to minHeap, move the top element from maxHeap to minHeap.\n    - If minHeap has more than one extra element compared to maxHeap, move the top element from minHeap to maxHeap.\n4. **Find Median**:\n    - If maxHeap has more elements, the median is `maxHeap.top()`.\n    - If minHeap has more elements, the median is `minHeap.top()`.\n    - If both heaps have the same number of elements, the median is the average of the tops of both heaps.\n\n# Complexity\n- Time complexity: $$O(log n)$$ \n\n- Space complexity: $$O(1)$$\n\n# Code\n```\nclass MedianFinder {\npublic:\n    priority_queue<int, vector<int>, greater<int> > minHeap;\n\tpriority_queue<int> maxHeap;\n    MedianFinder() {}\n    \n    void addNum(int num) {\n        maxHeap.push(num);\n        //check if all elements in maxHeap are smaller than all in minHeap.\n        //if not, then pop the top from maxHeap and push it to minHeap.\n        if(!minHeap.empty() && !maxHeap.empty() && maxHeap.top() > minHeap.top()) {\n            minHeap.push(maxHeap.top());\n            maxHeap.pop();\n        }\n        //check for balancing size of the heaps\n        if(maxHeap.size() > minHeap.size()+1) {\n            minHeap.push(maxHeap.top());\n            maxHeap.pop();\n        }\n        if(minHeap.size() > maxHeap.size()+1) {\n            maxHeap.push(minHeap.top());\n            minHeap.pop();\n        }\n    }\n    \n    double findMedian() {\n        if(minHeap.size() > maxHeap.size()) return minHeap.top();\n        if(maxHeap.size() > minHeap.size()) return maxHeap.top();\n        else return ( minHeap.top() + maxHeap.top())/2.0;\n    }\n};\n```
['Heap (Priority Queue)', 'C++']