# Question

Formatted question description: https://leetcode.ca/all/295.html

Hard

## Description

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

For example, [2,3,4], the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5

Design a data structure that supports the following two operations:

• void addNum(int num) - Add a integer number from the data stream to the data structure.
• double findMedian() - Return the median of all elements so far.

Example:

addNum(1)
findMedian() -> 1.5
findMedian() -> 2


1. If all integer numbers from the stream are between 0 and 100, how would you optimize it?
2. If 99% of all integer numbers from the stream are between 0 and 100, how would you optimize it?

# Algorithm

Since the data in the data stream is not in order, we should first think of a way to make it in ordered. If we use a vector to save the data stream, we must sort the array every time a new data comes in, which is not efficient.

Use large and small heaps to solve the problem, where the large heap holds the larger numbers in the right half, and the small heap holds the smaller arrays in the left half. In this way, the entire array is divided into two sections in the middle. Since the heap is saved from large to small, we hope that the data in the large pile is from small to large, so it is convenient to take the first one to calculate the median.

If all integer numbers from the stream are between 0 and 100, how would you optimize it?

• We can maintain an integer array of length 100 to store the count of each number along with a total count. Then, we can iterate over the array to find the middle value to get our median. Time and space complexity would be O(100) = O(1).

If 99% of all integer numbers from the stream are between 0 and 100, how would you optimize it?

• In this case, we can keep a counter for lessThanHundred and greaterThanHundred. As we know the solution will be definitely in 0-100 we don’t need to know those number which are >100 or <0, only count of them will be enough.

Java