Two Heaps with the Follow Up's Solution
Leetcode 295. Find Median from Data Stream.\n\n\n# Intuition\n\nWe can simply use a $\texttt{ArrayList}$ to record the number and sort the list, then we can eas
[Leetcode](https://leetcode.com/) [295. Find Median from Data Stream](https://leetcode.com/problems/find-median-from-data-stream/).\n\n\n# Intuition\n\nWe can simply use a $\\texttt{ArrayList}$ to record the number and **sort** the list, then we can easily get the **median** element of the list. However, the **Time Complexity** will be $O(n^2logn)$ and the **Space Complexity** is $O(n)$. \n\nIt surely will be **TLE** and we have to find a better solution.\n\n\n# Heap\n\nWe can use Two **Priority Queues** (Heaps) to maintain the data of the entire data stream. \n\nThe **min Heap** denoted as $\\textit{queueMin}$ is used to maintain the number $\\textit{num} \\leq \\textit{median}$. The **max Heap** denoted as $\\textit{queueMax}$ is used to maintain the number $\\textit{num} \\gt \\textit{median}$.\n\n- When the total number of data stream elements is **Even**: $\\texttt{queueMax.size()} = \\texttt{queueMin.size()}$, the dynamic median is $\\frac{\\texttt{queueMax.peek()} + \\texttt{queueMin.peek()}}{2}$;\n\n- When the total number of data stream elements is **Odd**: $\\texttt{queueMin.size()} = \\texttt{queueMin.size()} + 1$, the dynamic median is $\\texttt{queueMin.peek()}$.\n\nWhen we try to add a new number $\\textit{num}$ to the **Two Heaps**, the cases can be as follows:\n\n- $\\textit{num} \\leq \\max \\{\\textit{queMin}\\}$\n\nWe need to add this number to $\\textit{queueMin}$. The new median will be less than or equal to the original median, so we may need to move the $\\texttt{queueMin.peek()}$ to $\\textit{queueMax}$.\n\n- $\\textit{num} \\gt \\max \\{\\textit{queMin}\\}$\n\nWe need to add this number to $\\textit{queueMax}$. The new median will be greater than or equal to the original median, so we may need to move the $\\texttt{queueMax.peek()}$ to $\\textit{queueMin}$.\n\n\n```java\n    static class MedianFinder {\n        PriorityQueue<Integer> queueMin;\n        PriorityQueue<Integer> queueMax;\n\n        public MedianFinder() {\n            queueMin = new PriorityQueue<>((a, b) -> b - a);\n            queueMax = new PriorityQueue<>(((a, b) -> a - b));\n        }\n\n        public void addNum(int num) {\n            if (queueMin.isEmpty() || num <= queueMin.peek()) {\n                queueMin.offer(num);\n\n                if (queueMax.size() + 1 < queueMin.size()) {\n                    queueMax.offer(queueMin.poll());\n                }\n            } else {\n                queueMax.offer(num);\n\n                if (queueMin.size() < queueMax.size()) {\n                    queueMin.offer(queueMax.poll());\n                }\n            }\n        }\n\n        public double findMedian() {\n            if (queueMin.size() > queueMax.size()) {\n                return queueMin.peek();\n            }\n\n            return (queueMin.peek() + queueMax.peek()) / 2.0;\n        }\n    }\n```\n\n## Analysis\n\n- **Time Complexity**: $O(nlogn)$\n- **Space Complexity**: $O(n)$\n\n\n# Follow Ups\n\n#### If all integer numbers from the stream are in the range [0, 100], how would you optimize your solution?\n\n- We can use a bucket with a length of $101$. Each bucket stores the number of occurrences of each number, and records the total number of elements in the data stream. When searching for the median, calculate the number of the median, and then scan all buckets from front to back to get the answer.\n\n#### If 99% of all integer numbers from the stream are in the range [0, 100], how would you optimize your solution?\n\n- As last question, we can still use buckets to store the data. Then use **Two Pointers** to maintain the median. For the number out of range, we can use two arrays to record the number which less than $0$ or greater than $100$. If the median is not in $[0, 100]$, we can perform brute force to find it.\n\n------------\n\nAll suggestions are welcome. \nIf you have any query or suggestion please comment below.\nPlease upvote\uD83D\uDC4D if you like\uD83D\uDC97 it. Thank you:-)\n\nExplore More [Leetcode Solutions](https://leetcode.com/discuss/general-discussion/1868912/My-Leetcode-Solutions-All-In-One). \uD83D\uDE09\uD83D\uDE03\uD83D\uDC97\n\n
['Two Pointers', 'Sorting', 'Heap (Priority Queue)', 'Data Stream', 'Java']