Easy Solution Using 3 Approaches || Brute-Force || Binary Search || Priority Queue ||C++,Python,Java
Intuition\n Describe your first thoughts on how to solve this problem. \nThree approaches 1. bruteforce: sorting solution. 3. Using Binary Search 2. two heaps s
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThree approaches 1. bruteforce: sorting solution. 3. Using Binary Search 2. two heaps solution.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n* Initialize two heaps: small to store the smaller half of the numbers as a max heap and large to store the larger half of the numbers as a min heap.\nWhen adding a new number:\n  * If the number is greater than the smallest number in the large heap, push it to the large heap.\nOtherwise, push the negation of the number to the small heap.\nBalance the heaps by adjusting their sizes if necessary:\n  * If the size of the small heap becomes greater than the size of the large heap by more than one, pop the maximum element from the small heap and push it to the large heap.\n  * If the size of the large heap becomes greater than the size of the small heap by more than one, pop the minimum element from the large heap and push its negation to the small heap.\nTo find the median:\n  * If the sizes of the heaps are equal, the median is the average of the maximum element in the small heap and the minimum element in the large heap.\n  * Otherwise, the median is the maximum element in the small heap if its size is greater, or the minimum element in the large heap if its size is greater.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n    Adding a number takes O(log n) time, where n is the number of elements in the heaps.\n    Finding the median takes O(1) time.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n    The space complexity is O(n), where n is the number of elements stored in the heaps.\n\n* Brute-Force Solution\n```python []\nimport statistics\nclass MedianFinder:\n\n    def __init__(self):\n        self.arr=[]\n\n    def addNum(self, num: int) -> None:\n        \n        self.arr.append(num)\n        \n\n    def findMedian(self) -> float:\n        self.arr.sort()\n        return statistics.median(self.arr)\n        \n\n\n# Your MedianFinder object will be instantiated and called as such:\n# obj = MedianFinder()\n# obj.addNum(num)\n# param_2 = obj.findMedian()\n```\n```java []\nimport java.util.ArrayList;\nimport java.util.Collections;\n\nclass MedianFinder {\n\n    private ArrayList<Integer> arr;\n\n    public MedianFinder() {\n        arr = new ArrayList<>();\n    }\n\n    public void addNum(int num) {\n        arr.add(num);\n    }\n\n    public double findMedian() {\n        Collections.sort(arr);\n        int size = arr.size();\n        if (size % 2 == 0) {\n            return (arr.get(size / 2 - 1) + arr.get(size / 2)) / 2.0;\n        } else {\n            return arr.get(size / 2);\n        }\n    }\n```\n\n```C++ []\nclass MedianFinder {\nprivate:\n    std::vector<int> arr;\n\npublic:\n    MedianFinder() {\n        // No initialization needed for vector, it\'s done automatically\n    }\n\n    void addNum(int num) {\n        arr.push_back(num);\n    }\n\n    double findMedian() {\n        std::sort(arr.begin(), arr.end());\n        int size = arr.size();\n        if (size % 2 == 0) {\n            return (arr[size / 2 - 1] + arr[size / 2]) / 2.0;\n        } else {\n            return arr[size / 2];\n        }\n    }\n};\n\n```\n\n* Binary Search Solution \n   * Using Binary Search we can reduce complexity for adding num\n\n```python []\nclass MedianFinder:\n\n    def __init__(self):\n        self.arr=[]\n\n    def addNum(self, num: int) -> None:\n    \n        beg=0\n        end=len(self.arr)\n        while beg<end:\n            mid=(end+beg)//2\n            \n            if self.arr[mid]>num:\n                end=mid\n            else:\n                beg=mid+1\n        \n        self.arr.insert(beg,num)\n\n\n    def findMedian(self) -> float:\n        n=len(self.arr)\n        if n%2==1:\n            return self.arr[n//2]\n        else:\n            return (self.arr[n//2-1]+self.arr[n//2])/2\n        \n\n\n# Your MedianFinder object will be instantiated and called as such:\n# obj = MedianFinder()\n# obj.addNum(num)\n# param_2 = obj.findMedian()\n```\n```C++ []\nclass MedianFinder {\nprivate:\n    std::vector<int> arr;\n\npublic:\n    MedianFinder() {\n        // No initialization needed for vector, it\'s done automatically\n    }\n\n    void addNum(int num) {\n        // Binary search to find the correct position to insert\n        int beg = 0;\n        int end = arr.size();\n        while (beg < end) {\n            int mid = (end + beg) / 2;\n            if (arr[mid] > num) {\n                end = mid;\n            } else {\n                beg = mid + 1;\n            }\n        }\n        arr.insert(arr.begin() + beg, num);\n    }\n\n    double findMedian() {\n        int n = arr.size();\n        if (n % 2 == 1) {\n            return arr[n / 2];\n        } else {\n            return (arr[n / 2 - 1] + arr[n / 2]) / 2.0;\n        }\n    }\n};\n\n```\n```java []\nimport java.util.ArrayList;\nimport java.util.Collections;\n\nclass MedianFinder {\n\n    private ArrayList<Integer> arr;\n\n    public MedianFinder() {\n        arr = new ArrayList<>();\n    }\n\n    public void addNum(int num) {\n        int beg = 0;\n        int end = arr.size();\n        while (beg < end) {\n            int mid = (end + beg) / 2;\n            if (arr.get(mid) > num) {\n                end = mid;\n            } else {\n                beg = mid + 1;\n            }\n        }\n        arr.add(beg, num);\n    }\n\n    public double findMedian() {\n        int n = arr.size();\n        if (n % 2 == 1) {\n            return arr.get(n / 2);\n        } else {\n            return (arr.get(n / 2 - 1) + arr.get(n / 2)) / 2.0;\n        }\n    }\n\n```\n* Using Priority Queue\n\n```python []\nclass MedianFinder:\n    def __init__(self):\n        """\n        initialize your data structure here.\n        """\n        # Initialize two heaps: small to store the smaller half as a max heap\n        # and large to store the larger half as a min heap\n        self.small, self.large = [], []\n\n    def addNum(self, num: int) -> None:\n        # If large heap is not empty and the number is greater than the smallest number in large heap,\n        # push it to the large heap. Otherwise, push the negation of the number to the small heap.\n        if self.large and num > self.large[0]:\n            heapq.heappush(self.large, num)\n        else:\n            heapq.heappush(self.small, -1 * num)\n\n        # Balance the heaps by adjusting their sizes if necessary\n        if len(self.small) > len(self.large) + 1:\n            val = -1 * heapq.heappop(self.small)\n            heapq.heappush(self.large, val)\n        if len(self.large) > len(self.small) + 1:\n            val = heapq.heappop(self.large)\n            heapq.heappush(self.small, -1 * val)\n\n    def findMedian(self) -> float:\n        # If sizes of both heaps are equal, return the average of the maximum element in the small heap\n        # and the minimum element in the large heap\n        if len(self.small) > len(self.large):\n            return -1 * self.small[0]\n        elif len(self.large) > len(self.small):\n            return self.large[0]\n        return (-1 * self.small[0] + self.large[0]) / 2.0\n```\n```C++ []\nclass MedianFinder {\npublic:\n    MedianFinder() {\n        \n    }\n    \n    void addNum(int num) {\n        if (lower.empty()) {\n            // If lower heap is empty, push the number directly to it\n            lower.push(num);\n            return;\n        }\n        \n        if (lower.size() > higher.size()) {\n            if (lower.top() > num) {\n                // If lower heap size is greater than higher heap size and the number is less than the\n                // top element of the lower heap, push it to the higher heap after swapping the top\n                // element of the lower heap with the number\n                higher.push(lower.top());\n                lower.pop();\n                lower.push(num);\n            } else {\n                // If the number is greater than or equal to the top element of the lower heap,\n                // push it directly to the higher heap\n                higher.push(num);\n            }\n        } else {\n            if (num > higher.top()) {\n                // If higher heap size is greater than or equal to lower heap size and the number is\n                // greater than the top element of the higher heap, push it to the lower heap after\n                // swapping the top element of the higher heap with the number\n                lower.push(higher.top());\n                higher.pop();\n                higher.push(num);\n            } else {\n                // If the number is less than or equal to the top element of the higher heap,\n                // push it directly to the lower heap\n                lower.push(num);\n            }\n        }\n    }\n    \n    double findMedian() {\n        double result = 0.0;\n        \n        if (lower.size() == higher.size()) {\n            // If both heaps are of equal size, return the average of their top elements\n            result = lower.top() + (higher.top() - lower.top()) / 2.0;\n        } else {\n            // If lower heap size is greater than higher heap size, return the top element of the lower heap\n            // Otherwise, return the top element of the higher heap\n            result = (lower.size() > higher.size()) ? lower.top() : higher.top();\n        }\n        \n        return result;\n    }\nprivate:\n    priority_queue<int> lower;  // Max heap\n    priority_queue<int, vector<int>, greater<int>> higher;  // Min heap\n};\n```\n```java []\nprivate PriorityQueue<Integer> small = new PriorityQueue<>(Collections.reverseOrder());\nprivate PriorityQueue<Integer> large = new PriorityQueue<>();\nprivate boolean even = true;\n\npublic double findMedian() {\n    if (even)\n        return (small.peek() + large.peek()) / 2.0;\n    else\n        return small.peek();\n}\n\npublic void addNum(int num) {\n    if (even) {\n        large.offer(num);\n        small.offer(large.poll());\n    } else {\n        small.offer(num);\n        large.offer(small.poll());\n    }\n    even = !even;\n}\n```\n\n
['C++', 'Java', 'Python3']