# [LeetCode][295. Find Median from Data Stream] Two Heaps with the Follow Ups

*By Long Luo*

This article is the solution Two Heaps with the Follow Up's Solution of Problem 295. Find Median from Data Stream.

# Intuition

We 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)\).

It surely will be **TLE** and we have to find a better solution.

# Heap

We can use Two **Priority Queues** (Heaps) to maintain the data of the entire data stream.

The **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}\).

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}\);When the total number of data stream elements is

**Odd**: \(\texttt{queueMin.size()} = \texttt{queueMin.size()} + 1\), the dynamic median is \(\texttt{queueMin.peek()}\).

When we try to add a new number \(\textit{num}\) to the **Two Heaps**, the cases can be as follows:

- \(\textit{num} \leq \max \{\textit{queMin}\}\)

We 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}\).

- \(\textit{num} \gt \max \{\textit{queMin}\}\)

We 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}\).

1 | static class MedianFinder { |

## Analysis

**Time Complexity**: \(O(nlogn)\)**Space Complexity**: \(O(n)\)

# Follow Ups

#### If all integer numbers from the stream are in the range [0, 100], how would you optimize your solution?

- 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.

#### If 99% of all integer numbers from the stream are in the range [0, 100], how would you optimize your solution?

- 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.

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗