🔥🔥🔥INTERVIEW SOLUTION EASY TO UNDERSTAND 🔥🔥🔥🔥🔥
Intuition\n Describe your first thoughts on how to solve this problem. \n//median  can be obtained by keeping track of middle element or middle two elements \n\
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n//median  can be obtained by keeping track of middle element or middle two elements \n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n//we maintian two containers here , the first container stores the lower half elemnts and the second container stores the greater half elements,first half makes use of max heap and the second half makes use of min heap ,so that we can easily identify to which container our new incoming element will belong to (we always store the extra element in the first half,in this implementation )\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nwe are performing two operation everytime //either simply push an element or extract min and push an element \n//each of these operation takes o(log n )time \ntherefore the time complexity is o(nlogn)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n//corresponds to height of the heap that is o(log n) in total\n\n# Code\n```\nclass MedianFinder {\npublic:\n    priority_queue<int>s;//first containner to store smaller half elements\n    priority_queue<int,vector<int>,greater<int>>g;//this is our second congtainer to store greater half elements\n    int size;\n    MedianFinder() {\n        size=0;\n    }\n    \n    void addNum(int num) {\n        //we maintain extra element in our first container\n        if(size==0)\n        {\n            s.push(num);\n            size++;\n        }\n        else if(s.size()>g.size())\n        {\n                /*this time we need to make the size of both the    containers same //we check if the new element is lesser than \n    maximum elemnt of first container ,if so we transfer the maximum\n    elemnt from first container to second conatiner and add new\n    incoming element to the first conatiner\n    ( first container elements should be smaller than\n    second container elements)*/\n            if(num<s.top())\n            {\n                g.push(s.top());\n                s.pop();\n                s.push(num);\n            }\n            else\n            {\n                g.push(num);\n            }\n        }\n        else\n        {\n                //both are of same size;\n                /*if both are of same size we need to\n        add extra element to first container , we check\n        if new incoming element is greater than minimum\n        element in max heap(second container) if so we \n        transfer that minimum element to first container \n        and add new incoming elemnet to second conatiner*/\n           if(num>g.top())\n           {\n                s.push(g.top());\n                g.pop();\n                g.push(num);\n           }\n           else\n           {\n               s.push(num);\n           }\n        }\n    }\n    \n    double findMedian() {\n        if(s.size()>g.size())\n        {\n            return s.top();\n        }\n        else\n        {\n            return (s.top()+g.top())/2.0;\n\n        }\n    }\n};\n\n/**\n * Your MedianFinder object will be instantiated and called as such:\n * MedianFinder* obj = new MedianFinder();\n * obj->addNum(num);\n * double param_2 = obj->findMedian();\n */\n```
['C++']