295. Find Median from Data Stream

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.

Examples: 

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

For example:

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

Solution:

The brutal force is using insertion sort to an arraylist.

Time complexity: O(n^2) for addNum and O(1) for findMedian

My solution is using two priority queue to keep first half and second half of the numbers that we added so far. 

Time complecity: O(nlgn) for addNum and O(1) for findMedian

Eg. we have Max Priority Queue, and Min Priority Queue,

1.add num 1

   we first add to min priority queue => 1, then poll a number from min Priority queue which is 1  and add it to max priority queue

  max Priority Queue: =>1 , min Priority Queue : empty

2.add num 3

  we first add to max priority queue => 1,3, then poll a number from min Priority queue which is 3  and add it to max priority queue

 max Priority Queue: =>1 , min Priority Queue =>3

3. add num 5,

  we first add to min priority queue => 3,5, then poll a number from min Priority queue which is 3  and add it to max priority queue

  max Priority Queue: =>1,3 , min Priority Queue => 5

4. add num 2

 we first add to max priority queue => 1,2,3, then poll a number from min Priority queue which is 3  and add it to max priority queue

 max Priority Queue: =>1,2 , min Priority Queue =>3, 5

The invariant here is max PQ will always have the first half of the sorted elements while max PQ will always have the second half of the sorted elements.

findMedian is very intuitive. 

 class MedianFinder {  
   PriorityQueue<Integer> pqMin;  
   PriorityQueue<Integer> pqMax;  
   /** initialize your data structure here. */  
   public MedianFinder() {  
     pqMin=new PriorityQueue<Integer>();  
     pqMax=new PriorityQueue<Integer>(20,Collections.reverseOrder());  
   }  
   public void addNum(int num) {  
     if(pqMin.size()==pqMax.size()){  
       pqMin.offer(num);  
       pqMax.offer(pqMin.poll());  
     }  
     else{  
       pqMax.offer(num);  
       pqMin.offer(pqMax.poll());  
     }  
   }  
   public double findMedian() {  
     if(pqMin.size()==pqMax.size()){  
       return (pqMin.peek()+pqMax.peek())/2.0;  
     }  
     else{  
       return (double)pqMax.peek();  
     }  
   }  
 }