# 295. Find Median from Data Stream!

{% hint style="info" %}
two PriorityQueue
{% endhint %}

```java
class MedianFinder {

    // min heap
    // java defaul priority queue is min heap
    // use min heap to keep large numbers
    PriorityQueue<Integer> large = new PriorityQueue<>();
    // use max heap to store small numbers
    PriorityQueue<Integer> small = new PriorityQueue<>((a,b)->b-a);
    /** initialize your data structure here. */
    public MedianFinder() {
        
    }
    
    public void addNum(int num) {
        // make small.size()>=large.size();
        if(small.size()>large.size()){
            //method: offer
            large.offer(num);
        }else{
            small.offer(num);
        }
        
        if(small.size() >0 && large.size()>0 && small.peek()>large.peek()){
            int temp=small.poll();
            small.offer(large.poll());
            large.offer(temp);
        }
    }
    
    public double findMedian() {
        if(small.size()==large.size()){
            // convert to float
            return (small.peek()+large.peek())/2.0;
        }else{
            return small.peek();
        }
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */
```

{% hint style="info" %}
follow-up question:<br>

**Follow up:**

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

Answer:

1

-we maintain HashMap -we also maintain total number of elements, so that median is just total-nums/2 th element from sorted array.&#x20;

-then we go over Map from 1-100 and count element, when we hit total-nums/2 th element , that is our median

2\.

add two variable to count the numbers that smaller and larger than 100 respectively.
{% endhint %}


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://ucan.gitbook.io/notes/design/untitled/295.-find-median-from-data-stream.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.