[Java] Detailed Code Solutions for Follow-Ups
Solution for main question\njava\n/**\n * Using two heaps\n * \n * Time Complexity:\n * 1) addNum -> O(5 * log (N/2)) = O(log N)\n * 2) findMedian -> O(1)\n *\n
**Solution for main question**\n```java\n/**\n * Using two heaps\n * \n * Time Complexity:\n * 1) addNum -> O(5 * log (N/2)) = O(log N)\n * 2) findMedian -> O(1)\n *\n * Space Complexity: O(N)\n *\n * N = Count of numbers in the data stream.\n */\nclass MedianFinder {\n    PriorityQueue<Integer> smallNums; // Max Heap\n    PriorityQueue<Integer> largeNums; // Min Heap\n\n    public MedianFinder() {\n        smallNums = new PriorityQueue<>(Collections.reverseOrder());\n        largeNums = new PriorityQueue<>();\n    }\n\n    public void addNum(int num) {\n        // Add to maxHeap first (Group of smaller numbers)\n        smallNums.offer(num);\n        // Balance the heaps\n        largeNums.offer(smallNums.poll());\n        if (largeNums.size() > smallNums.size()) {\n            smallNums.offer(largeNums.poll());\n        }\n    }\n\n    public double findMedian() {\n        if (smallNums.size() != largeNums.size()) {\n            return smallNums.peek();\n        }\n        return (smallNums.peek() + largeNums.peek()) / 2.0;\n    }\n}\n```\n\n---\n**Solution for Follow-Up 1**\n```java\n/**\n * Follow-Up 1 - Numbers are between [0, 100]\n * Maintain a cumulative count array.\n *\n * Time Complexity:\n * 1) addNum -> O(101) = O(1)\n * 2) findMedian -> O(log(101)) = O(1)\n *\n * Space Complexity: O(101) = O(1)\n */\nclass MedianFinder {\n    int[] count;\n\n    public MedianFinder() {\n        count = new int[101];\n    }\n\n    public void addNum(int num) {\n        for (int i = num; i < 101; i++) {\n            count[i]++;\n        }\n    }\n\n    public double findMedian() {\n        int totalNums = count[100];\n        int medianCount = totalNums % 2 == 0 ? totalNums / 2 : (totalNums + 1) / 2;\n        int idx = binarySearch(count, medianCount);\n        if (totalNums % 2 == 0) {\n            if (medianCount < count[idx]) {\n                return idx;\n            }\n            for (int i = idx + 1; i < 101; i++) {\n                if (count[i] > count[idx]) {\n                    return (idx + i) / 2.0;\n                }\n            }\n        }\n        return idx;\n    }\n\n    private int binarySearch(int[] nums, int target) {\n        int start = 0;\n        int end = nums.length - 1;\n        while (start < end) {\n            int mid = start + (end - start) / 2;\n            if (nums[mid] >= target) {\n                end = mid;\n            } else {\n                start = mid + 1;\n            }\n        }\n        return start;\n    }\n}\n```\n\n**Optimized addNum() function to true O(1)**\n```java\n/**\n * Follow-Up 1 - Numbers are between [0, 100]\n * Maintain a count array. Here Add num is optimized to true O(1)\n *\n * Time Complexity:\n * 1) addNum -> O(1)\n * 2) findMedian -> O(101) = O(1)\n *\n * Space Complexity: O(101) = O(1)\n */\nclass MedianFinder {\n    int[] count;\n    int totalNums;\n\n    public MedianFinder() {\n        count = new int[101];\n    }\n\n    public void addNum(int num) {\n        count[num]++;\n        totalNums++;\n    }\n\n    public double findMedian() {\n        int medianCount = totalNums % 2 == 0 ? totalNums / 2 : (totalNums + 1) / 2;\n        int countSum = 0;\n        int idx = 0;\n        while (idx <= 100) {\n            countSum += count[idx];\n            if (medianCount <= countSum) {\n                break;\n            }\n            idx++;\n        }\n        if (totalNums % 2 == 0) {\n            if (medianCount < countSum) {\n                return idx;\n            }\n            for (int i = idx + 1; i < 101; i++) {\n                if (count[i] != 0) {\n                    return (idx + i) / 2.0;\n                }\n            }\n        }\n        return idx;\n    }\n}\n```\n\n---\n**Solution for Follow-Up 2**\n```java\n/**\n * Follow-Up 2 - 99% Numbers are between [0, 100]\n * Until a threshold is met use two heaps to find the median. Once the threshold is met\n * use the cumulative count array.\n *\n * Time Complexity:\n * 1) addNum -> Until threshold O(101 + 5*log(threshold/2)). After threshold O(101)\n * 2) findMedian -> Until threshold O(1). After threshold O(101)\n *\n * Space Complexity: O(101+threshold)\n */\nclass MedianFinder {\n    int[] count;\n    int lessThanZero;\n    int totalNums;\n    int threshold;\n    PriorityQueue<Integer> smallNums; // Max Heap\n    PriorityQueue<Integer> largeNums; // Min Heap\n\n    public MedianFinder() {\n        count = new int[101];\n        threshold = 100;\n        smallNums = new PriorityQueue<>(Collections.reverseOrder());\n        largeNums = new PriorityQueue<>();\n    }\n\n    public void addNum(int num) {\n        if (num < 0) {\n            lessThanZero++;\n        }\n        for (int i = Math.max(num, 0); i < 101; i++) {\n            count[i]++;\n        }\n        totalNums++;\n        if (totalNums <= threshold) {\n            smallNums.offer(num);\n            largeNums.offer(smallNums.poll());\n            if (largeNums.size() > smallNums.size()) {\n                smallNums.offer(largeNums.poll());\n            }\n        }\n    }\n\n    public double findMedian() {\n        if (totalNums <= threshold) {\n            if (smallNums.size() != largeNums.size()) {\n                return smallNums.peek();\n            }\n            return (smallNums.peek() + largeNums.peek()) / 2.0;\n        }\n        int medianCount = totalNums % 2 == 0 ? totalNums / 2 : (totalNums + 1) / 2;\n        int idx = binarySearch(count, medianCount);\n        if (totalNums % 2 == 0) {\n            if (medianCount < count[idx]) {\n                return idx;\n            }\n            for (int i = idx + 1; i < 101; i++) {\n                if (count[i] > count[idx]) {\n                    return (idx + i) / 2.0;\n                }\n            }\n        }\n        return idx;\n    }\n\n    private int binarySearch(int[] nums, int target) {\n        int start = 0;\n        int end = nums.length - 1;\n        while (start < end) {\n            int mid = start + (end - start) / 2;\n            if (nums[mid] >= target) {\n                end = mid;\n            } else {\n                start = mid + 1;\n            }\n        }\n        return start;\n    }\n}\n```
['Heap (Priority Queue)', 'Java']