C++ 112 ms 99% solution w/ follow up
The idea behind this solution is to use two prioriy queues and two ints where int1 <= int2. The two ints store potential median, and the two priority queues sto
The idea behind this solution is to use two prioriy queues and two ints where int1 <= int2. The two ints store potential median, and the two priority queues stores values less than the int1, and greater than int 2. Thus, when we always have the median in ```O(1)``` time. When we add element, we insert according to int1 and int2, and int1/2 are potentially updated. Once that is done, we need to "shift" numbers either to left or right, so the size of the two queues are at most 1 apart. Thus, when the two queues are equal in size, median is average of int1 and int2, and when they are not equal, the median is either int1 or int2, depending on which queue you set to have the greater size.\n\nThe less queue must have elements sorted in ascending, so we always push out the maximum (previous element in sorted order), while the greater queue must have elements sorted in descending, so we always push out the minimum (next element in sorted order)\n\nThe run-time of this algorithm is ```O(nlgn)```, and space complexity is ```O(n)```. \n\n**Follow up**:\n\nIf the range of the numbers are between 0 and 100, we can use bins to collect the frequency of each number. This makes the insert process ```O(1)```. To get the median, we can simply check what is the cumulative count (if 500 elements inserted, median is the 250th and 251th number. we need to find after which element do we go over count 250 and 251, so we add count for 0, count for 1, etc. until we get to elements covering 250 and 251). This can be done in ```O(1)``` time, since we go at most from 0 up to 100. \n\nIf 99% of the numbers are in ```[0, 100]``` but 1% is not, we can simply have two extra counts, one for less than 0, one for greater than 100. This is because we know for sure the median is still in ```[0, 100]``` since it occupies more than 50% of the total counts, so we don\'t need the values for those 1%. Thus, we simply add in two extra counts when calculating the cumulative count value for median, and do the same thing as before to find the median. For example if we have 107 elements inserted, and there are 2 elements before 0 and 5 after 100. Since total elements = 107, we are looking for 54th element, so we start with count = 2, add count for 0, for 1, etc. until we get the element that increases count over 54.\n\n```\nclass MedianFinder {\npublic:\n    MedianFinder(): size(0), v1(0), v2(0) {} // Assert size of g is either equal or greater than 1 than size of l\n    \n    void addNum(int num) {\n        ++size;\n        if(size == 1) v2 = num;\n        else if(size == 2) {\n            v1 = num;\n            if(v1 > v2) swap(v1, v2);\n        }\n        else {\n            if(num >= v2) g.push(num);\n            else if(num > v1) {g.push(v2); v2 = num;}\n            else l.push(num);\n        }\n        if(l.size() > g.size()) {\n            g.push(v2);\n            v2 = v1;\n            v1 = l.top(); l.pop();\n        }\n        else if(g.size() > l.size()+1) {\n            l.push(v1);\n            v1 = v2;\n            v2 = g.top(); g.pop();\n        }\n    }\n    \n    double findMedian() {\n        return size % 2 ? v2 : (v1 + v2)/2.0;\n    }\n    int size;\n    int v1;\n    int v2;\n    priority_queue<int, vector<int>, greater<int>> g;\n    priority_queue<int, vector<int>, less<int>> l;\n};\n\nauto gucciGang = []() {std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();\n```
[]