Building intuition || cpp || ✅
Approach 1 (maintaing a sorted Array)\n\n# Intuition\n-   Median : We can find median of a stream on data in O(1) time.\n-   Insertion : finding first elements 
# Approach 1 (maintaing a sorted Array)\n\n# Intuition\n-   **Median** : We can find median of a stream on data in O(1) time.\n-   **Insertion** : finding first elements in array less than num let it be *i*. Inserting element just before *i*.\n\n# Complexity\n- Time complexity: \n    $$O(n)$$ (for insertion)\n    $$O(1)$$ (for finding median)\n\n- Space complexity:\n    $$O(n)$$ (for storing data)\n\n# Code\n```\nclass MedianFinder {\nprivate:\n    vector<float> arr;\npublic:\n    MedianFinder() {\n        \n    }\n    \n    void addNum(float num) {\n        // Insert the number into the sorted array\n        int i = 0;\n        while (i < arr.size() && num > arr[i]) {\n            i++;\n        }\n        arr.insert(arr.begin() + i, num);\n    }\n    \n    double findMedian() {\n        int n = arr.size();\n        if (n % 2 == 0) {\n            return (arr[n / 2 - 1] + arr[n / 2]) / 2.0;\n        } else {\n            return arr[n / 2];\n        }        \n    }\n};\n\n```\n# Approach 2 (using minHeap and maxHeap)\n\n# Intuition\n- Median is basically an element such that half elements are greater than median and half elements are less than median. Put in a different way, median in *middle-most* element in a sorted array. \n- After, each insertion median can change by only one value(index wise) :\n    - To the *right* : if value inserted in less than median.\n    - To the *left* : if value inserted in more than median.\n- We can maintain two heaps to solve this problem for us i.e finding just left and right value of median (index wise) after an insertion\n    - minHeap : for storing values of right of median value\n    - maxHeap : for storing values of left of median value\n- After, each insertion we can update median value accordingly.\n# Complexity\n- Time complexity:\nInsertion : $$O(logn)$$ \nfindingMedian : $$O(1)$$ \n- Space complexity:\nfor heaps : $$O(n)$$  \n\n# Code\n```\nclass MedianFinder {\nprivate:\n    priority_queue<int> maxHeap; // Stores the smaller half of numbers\n    priority_queue<int, vector<int>, greater<int>> minHeap; // Stores the larger half of numbers\n    double median;\npublic:\n    MedianFinder() {\n        \n    }\n    \n    void addNum(int num) {\n        // Add the number to the appropriate heap\n        if (maxHeap.empty() || num <= maxHeap.top()) {\n            maxHeap.push(num);\n        } else {\n            minHeap.push(num);\n        }\n        \n        // Rebalance heaps if necessary\n        if (maxHeap.size() > minHeap.size() + 1) {\n            minHeap.push(maxHeap.top());\n            maxHeap.pop();\n        } else if (minHeap.size() > maxHeap.size()) {\n            maxHeap.push(minHeap.top());\n            minHeap.pop();\n        }\n    }\n    \n    double findMedian() {\n        if (maxHeap.size() == minHeap.size()) {\n            // If the number of elements is even, take the average of the two middle elements\n            return (maxHeap.top() + minHeap.top()) / 2.0;\n        } else {\n            // If the number of elements is odd, the median is the top of the max heap\n            return maxHeap.top();\n        }\n    }\n};\n```\n\n
['C++']